← 返回题目列表

AtCoder · awc0094_a

A. 不断增长的史莱姆

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

分数: 233 分

问题陈述

高桥正在玩 RPG 游戏。

在这个游戏中,有一个地牢,包括 N 房间排列成一排。房间有编号 1, 2, \ldots, N 从入口到后面,每个房间都有一只怪物在里面等待。房间里的怪物实力 i (1 \leq i \leq N) is V_i.

高桥控制着一条初始强度为 W 征服这个地牢。史莱姆按照从房间开始的顺序访问每个房间一次 1 到房间 N,按顺序访问它们 1, 2, \ldots, N。它不能返回或跳过房间。

史莱姆访问房间时的“当前强度”被定义为初始强度 W 加上访问该房间之前吸收的所有怪物的总力量。

当史莱姆来到房间时 i,恰好发生以下两种情况之一:

  • 如果怪物的力量 V_i is 小于或等于 史莱姆的当前强度(包括以下情况) V_i 等于史莱姆当前的强度),史莱姆吸收怪物。 V_i 立即添加到史莱姆的强度中,添加后的值成为后续房间的当前强度。
  • 如果怪物的力量 V_i is 严格大于 史莱姆当前的强度,史莱姆无法吸收怪物,并且史莱姆的强度不会改变。

找出史莱姆访问过所有房间后的强度 1 到房间 N 按顺序。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq 10^9
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数。
  • 保证答案小于 2^{63} (它适合签名的 64位整数)。但是,它可能超出签名的范围 32位整数 (2^{31}-1 或更少)。

输入

N W
V_1 V_2 \cdots V_N
  • 第一行包含一个整数 N 代表房间数和一个整数 W 代表史莱姆的初始强度,以空格分隔。
  • 第二行包含整数 V_1, V_2, \ldots, V_N 代表每个房间中怪物的强度,以空格分隔。

输出

在单行上以整数形式输出征服地牢后史莱姆的强度。


示例输入 1

5 3
2 4 1 3 7

示例输出 1

20

示例输入 2

8 5
3 6 2 10 4 8 1 20

示例输出 2

59

示例输入 3

10 1
1 3 2 5 100 4 6 3 2 1000000000

示例输出 3

19