分数: 366 分
问题陈述
高桥在图书馆兼职。图书馆有一个书架,上面有 N 书籍排成一排,高桥被指派来整理这个书架。
书籍编号为 1 to N 从左到右,整理书籍 i (1 \leq i \leq N) 需要 A_i 分钟。由于高桥只有 K 今天轮班可用的分钟数,他可能无法整理整个书架。
因此,高桥决定选择 一个连续的间隔 从书架中取出 并整理该区间内的所有书籍。具体来说,他选择整数 l, r (1 \leq l \leq r \leq N)并组织书中的所有书籍 l 预订 r。组织所需的总时间为 A_l + A_{l+1} + \cdots + A_r 分钟。
Takahashi 希望选择一个间隔,使得总组织时间最多为 K 分钟。在满足该条件的所有区间中,最大化组织的书籍数量, r - l + 1.
换句话说,找到最大值 r - l + 1 所有整数对 (l, r) (1 \leq l \leq r \leq N)令人满意
A_l + A_{l+1} + \cdots + A_r \leq K
但是,如果没有这样的 (l, r) 存在,即如果 A_i > K 对于所有人 i (1 \leq i \leq N),输出 0.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{15}
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数
输入
N K A_1 A_2 \cdots A_N
- 第一行包含一个整数 N 代表书籍数量和一个整数 K 代表高桥可用的时间(以分钟为单位),以空格分隔。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 代表组织每本书所需的时间(以分钟为单位),以空格分隔。
输出
输出高桥可以在一行中组织的最大书籍数量。如果不存在满足条件的区间,则输出 0.
示例输入 1
5 10 3 1 4 1 5
示例输出 1
4
示例输入 2
8 15 5 2 6 3 1 2 4 7
示例输出 2
5
示例输入 3
10 1000000000000 500000000 200000000 300000000 100000000 400000000 600000000 150000000 250000000 350000000 450000000
示例输出 3
10