← 返回题目列表

AtCoder · awc0099_a

A. 链桶

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

分数: 266 分

问题陈述

高桥正在进行一项利用雨水收集雨水的实验 N 水桶。桶的编号从 1 to N和桶 i 容量为 C_i 升。最初,所有桶都是空的。

水桶连接成一条线,水流如下。高桥连续倒了总共 W 升水放入桶中 1。流入水桶的水 i (1 \leq i \leq N-1) 积聚在桶中 i 直到到达桶 i的容量 C_i。后斗 i 已满(恰好 C_i 升水已累积),流入水桶的任何额外水 i 将全部流入桶中 i+1。后斗 N 满了,任何额外流入的水都会溢出并消失。

确定倒完所有水后装满的桶的数量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq 10^{18}
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入均为整数

输入

N W
C_1 C_2 \cdots C_N
  • 第一行包含一个整数 N 代表桶的数量和一个整数 W 代表要倒入的水总量(以升为单位),以空格分隔。
  • 第二行包含整数 C_1, C_2, \ldots, C_N 代表每个桶的容量,以空格分隔。
  • C_i 代表桶的容量(单位为升) i.

输出

在一行中打印已满的桶的数量。


示例输入 1

3 10
3 4 5

示例输出 1

2

示例输入 2

5 25
5 10 3 8 6

示例输出 2

3

示例输入 3

6 1000000000000000000
100000000 200000000 300000000 400000000 500000000 600000000

示例输出 3

6