← 返回题目列表

AtCoder · colopl2018_qual_d

D. Snuke Sodate - 训练 -

中文机器翻译题面 查看原题

配点 : 500 点

問題文

您正在享受“Snuke Sodate”。您想让您心爱的斯努克成为最聪明的猫,因此您决定对他进行一些大脑训练。

在《Snuke Sodate》中,你可以花费“体力”来训练Snuke的智力。耐力 1 每消耗一次,斯努克的智力就会增加。 它将上涨 1 。

耐力为1 每单位时间 最多只有 1 恢复到 X 。最大耐力 如果您已达到 X ,您的体力将不会随着时间的推移而恢复。 还有体力 不能小于 0 。初始状态,即时间 在 O 时,体力已满,即 仅累积了 X 。

当然,体力积累起来就消耗是最有效率的,可惜你在现实世界还有事情要做。 你不能一直玩“Snuke Figure”(现实生活往往是不灵活的)。

不过,您也许可以在忙碌的生活中抽出时间来推出“Snuke Sodate”。 N 我想出了一些。i 第二个候选者是时间 T_i 。 因为你太忙了,一旦开始游戏,你就得立刻消耗完体力并退出游戏。 也就是说,时间 T_i 有耐力 如果你还剩下 s ,你就会失去体力。 s 你可以消耗以下任意非负整数数量,并根据消耗的数量增加 Snuke 的智力。 无法进行其他操作。

现实生活中的计划很难实现,你可能无法掌握未来一段时间你会有多忙。因此,每个 K=1,2,...,N , 当我输入 N 游戏发布时间候选 如果你选择 K 或更少并开始游戏,我们决定计算Snuke最终的最大智力是多少。 这些 查找所有 N 值。

制約

  • 1 \leq N \leq 5000
  • 1 \leq X \leq 10^9
  • 1 \leq T_i \leq 10^9(1\leq i\leq N)
  • T_i < T_{i+1}(1\leq i\leq N-1)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N X
T_1
:
T_N

出力

各 K=1,2,...,N ,输出Snuke智力的最终最大值。


入力例 1

3 3
2
4
6

出力例 1

3
6
7

K=1 ,时间 将耐力添加到 4 耐力到 3 吃掉它吧。

K=2 ,时间 将耐力添加到 2 耐力到 3 消耗和时间 6 耐力到 3 吃掉它吧。

K=3 ,时间 将耐力添加到 2 耐力到 3 消耗和时间 4 耐力到 2 消耗和时间 6 耐力到 2 吃掉它吧。


入力例 2

5 4
4
5
7
8
11

出力例 2

4
8
11
11
11

入力例 3

7 5
2
4
10
12
13
17
20

出力例 3

5
10
15
18
20
22
22