/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は図書館でアルバイトをしています。図書館には N 冊の本が一列に並んだ本棚があり、高橋君はこの本棚の整理を任されました。
本は左から順に 1 から N までの番号が付いており、本 i（ 1 \leq i \leq N ）を整理するには A_i 分かかります。高橋君は今日の勤務で使える時間が K 分しかないため、本棚全体を整理することはできないかもしれません。
そこで高橋君は、本棚の中から 連続する区間を1つ 選び、その区間に含まれるすべての本を整理することにしました。具体的には、整数 l, r（ 1 \leq l \leq r \leq N ）を選び、本 l から本 r までのすべてを整理します。このとき、整理にかかる時間の合計は A_l + A_{l+1} + \cdots + A_r 分です。
高橋君は、整理にかかる時間の合計が K 分以下となるように区間を選びたいと考えています。条件を満たす区間の中で、整理できる本の冊数 r - l + 1 を最大化してください。
すなわち、
A_l + A_{l+1} + \cdots + A_r \leq K
を満たす整数の組 (l, r)（ 1 \leq l \leq r \leq N ）における r - l + 1 の最大値を求めてください。
ただし、条件を満たす (l, r) が1つも存在しない場合、つまりすべての i（ 1 \leq i \leq N ）について A_i > K である場合は、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
- 1 行目には、本の冊数を表す整数 N と、高橋君が使える時間（分）を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各本を整理するのにかかる時間（分）を表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
高橋君が整理できる本の最大冊数を 1 行で出力せよ。条件を満たす区間が存在しない場合は 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
Score : 366 pts
Problem Statement
Takahashi works part-time at a library. The library has a bookshelf with N books arranged in a row, and Takahashi has been assigned to organize this bookshelf.
The books are numbered from 1 to N from left to right, and organizing book i (1 \leq i \leq N) takes A_i minutes. Since Takahashi only has K minutes available for today's shift, he may not be able to organize the entire bookshelf.
Therefore, Takahashi has decided to choose one contiguous interval from the bookshelf and organize all the books within that interval. Specifically, he chooses integers l, r (1 \leq l \leq r \leq N) and organizes all books from book l to book r. The total time required for organizing is A_l + A_{l+1} + \cdots + A_r minutes.
Takahashi wants to choose an interval such that the total organizing time is at most K minutes. Among all intervals satisfying this condition, maximize the number of books organized, r - l + 1.
In other words, find the maximum value of r - l + 1 over all integer pairs (l, r) (1 \leq l \leq r \leq N) satisfying
A_l + A_{l+1} + \cdots + A_r \leq K
However, if no such (l, r) exists, that is, if A_i > K for all i (1 \leq i \leq N), output 0.
Constraints
- 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)
- All input values are integers
Input
N K A_1 A_2 \cdots A_N
- The first line contains an integer N representing the number of books and an integer K representing the time (in minutes) available to Takahashi, separated by a space.
- The second line contains N integers A_1, A_2, \ldots, A_N representing the time (in minutes) required to organize each book, separated by spaces.
Output
Output the maximum number of books Takahashi can organize in a single line. If no interval satisfying the condition exists, output 0.
Sample Input 1
5 10 3 1 4 1 5
Sample Output 1
4
Sample Input 2
8 15 5 2 6 3 1 2 4 7
Sample Output 2
5
Sample Input 3
10 1000000000000 500000000 200000000 300000000 100000000 400000000 600000000 150000000 250000000 350000000 450000000
Sample Output 3
10