← 返回题目列表

AtCoder · awc0056_c

C. 整理连续的书架

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

分数: 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