242039 - 闯关补给站

题目描述

小明正在参加一场闯关游戏,一共有 n 个关卡,需要按照顺序依次挑战。

小明初始拥有 E 点能量,能量最多只能达到 M 点。

每个关卡都有一个能量消耗值 c_i。如果当前能量不少于该关卡的消耗值,就可以成功通过该关卡,并扣除对应的能量:

E=E-c_i

此外,小明还拥有 p 张补给卡。

每张补给卡可以使用一次,使用后立即恢复 R 点能量,但能量不能超过最大值 M。

也就是说,使用补给卡后:

E=\min(E+R,M)

每次挑战关卡时,小明可以选择:

  • 直接消耗当前能量挑战。
  • 如果能量不足,并且还有补给卡,可以使用一张补给卡,然后再挑战。

如果使用补给卡后仍然无法满足当前关卡的能量要求,就无法继续闯关。

请你帮助小明计算:

  1. 最多能够连续通过多少个关卡?
  2. 闯关结束后还剩余多少能量?
  3. 最终剩余多少张补给卡?

注意:

  • 关卡必须按照给定顺序挑战,不能跳过。
  • 补给卡只能在挑战关卡之前使用。
  • 不要求必须使用完所有补给卡。
  • 如果当前能量足够通过关卡,就不需要主动使用补给卡。
输入

第一行输入四个整数 n,E,M,R,分别表示关卡数量、初始能量、最大能量和每张补给卡的恢复量。

第二行输入一个整数 p,表示补给卡数量。

第三行输入 n 个整数:

c_1,c_2,\ldots,c_n

表示每个关卡的能量消耗。

输出

输出一行三个整数,分别表示:

  • 最多通过的关卡数量。
  • 最终剩余能量。
  • 最终剩余补给卡数量。
样例

输入

5 10 15 10
2
6 7 5 9 4

输出

4 3 0
说明

样例解释

初始能量为 10,最多能量为 15,拥有 2 张补给卡。

关卡操作剩余能量剩余补给卡
初始初始状态102
1消耗 642
2补充 10,再消耗 771
3消耗 521
4补充 10,再消耗 930
5能量不足,无法继续30

因此,小明最多通过 4 个关卡,剩余 3 点能量和 0 张补给卡。

数据范围

对于所有测试数据,保证:

1\le n\le 2\times10^5

0\le E\le M\le 10^9

1\le R\le 10^9

0\le p\le 2\times10^5

1\le c_i\le 10^9

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 2
通过人数 2
金币数量 3 枚
难度 基础


上一题 下一题