← 返回题目列表

Codeforces · 2025/D

D. 属性检查

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

想象一个游戏,您扮演的角色具有两个属性:“力量”和“智力”,最初的等级为零。

在游戏过程中,您将获得 $$$m$$$ 属性点,这些属性点可让您提高属性等级 — 1 点将使其中一项属性提高一级。但有时候,你会遇到所谓的“属性检查”:如果你对应的属性足够高,你就会通过;如果你的属性足够高,你就会通过。否则,你就会失败。

花了一些时间,你终于准备了一份清单,其中包含你获得的所有积分和你所达到的所有检查的记录。现在您想知道:如果您明智地使用积分,一次运行中最多可以通过多少属性检查?

请注意,您无法更改记录的顺序。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le 5000$$$; $$$m < n \le 2 \cdot 10^6$$$) - 列表中的记录数以及您在游戏中获得的总分。

第二行包含 $$$n$$$ 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$-m \le r_i \le m$$$),其中 $$$r_i$$$ 编码第 $$$i$$$ 条记录:

- 如果$$$r_i = 0$$$,则第$$$i$$$记录为获取一个属性点。您可以花费来升级力量或智力;
- 如果$$$r_i > 0$$$,那么这是一次智力检定:如果你的智力水平大于或等于$$$|r_i|$$$,你就通过了。
- 如果$$$r_i < 0$$$,那么这是一次力量检查:如果你的力量水平大于或等于$$$|r_i|$$$,你就通过了。

输入的附加约束:序列 $$$r_1, r_2, \dots, r_n$$$ 恰好包含等于 $$$0$$$ 的 $$$m$$$ 元素。

输出

打印一个整数 — 您可以通过的最大检查次数。

示例

输入 #1

10 5
0 1 0 2 0 -3 0 -4 0 -5

输出 #1

3

输入 #2

3 1
1 -1 0

输出 #2

0

输入 #3

9 3
0 0 1 0 2 -3 -2 -2 1

输出 #3

4

注意

在第一个测试中,最好将每一点都花在力量上,因此你将无法通过 $$$2$$$ 智力检查,但通过 $$$3$$$ 力量检查。

在第二个测试中,您将无法通过两项检查,因为您获得的第一点是在检查之后。

在第三次测试中,最佳策略之一是:

1.在智力上花费第一点;
2.将第二点花在力量上;
3.将第三点花在力量上;