← 返回题目列表

AtCoder · utpc2021_f

F. 红蓝奖牌

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

配点 : 100 点

問題文

你遇到了一群魔物。魔物群由 N 只魔物组成,排列在你面前的一列中。从前面开始,第 i 只魔物的体力为 h_i 。

你通过以下 2 种类型的攻击进行区分,决定击败所有魔物。

  • 用剑攻击。对最前面的存活魔物造成与其剩余体力相同的伤害。
  • 用枪攻击。对所有存活魔物各造成 1 点伤害。

体力将会被给予。 0 体力为零的魔物将会消失。

你有一名直属上司。 2 每次发动攻击时, 1 根据该次攻击造成的伤害量,你将从上司那里获得作为奖励的勋章。

1 从第一位上官处,如果对魔物造成的总伤害达到了 k_1 以上,将会授予红色勋章 1 枚。
2 从第一位上官处,如果对魔物造成的总伤害达到了 k_2 以上则会授予蓝色勋章 1 枚。

当消灭所有魔物时,请求红色勋章和蓝色勋章的总数可能达到的最大值。

制約

  • 所有输入均为整数
  • 1 \le N \le 2 \times 10^5
  • 1 \le k_1 \le k_2 \le 2 \times 10^5
  • 1 \le h_i \le 2 \times 10^5

部分点

  • k_1 = k_2 的数据集 给出 30 点。 如果您正确回答了所有满足

入力

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

N k_1 k_2
h_1 \ldots h_N

出力

答案 请打印除以 1 行输出。


入力例 1

4 2 3
3 2 1 1

出力例 1

4

可以按如下方式进行攻击。

  • 用剑攻击。3 造成伤害,并获得红色勋章和蓝色勋章。
  • 用剑攻击。2 造成伤害,并获得红色勋章。
  • 用矛攻击。2 造成伤害,并获得红色勋章。

入力例 2

5 4 5
2 2 2 2 2

出力例 2

4

入力例 3

15 4 7
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

出力例 3

16