/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は倉庫の整理を任されている。倉庫には N 個の荷物が一列に並んでおり、左から i 番目の荷物の重さは A_i である。
高橋君はトラックを使って荷物を搬出する。高橋君は以下の搬出操作を好きな回数（0 回でもよい）繰り返し行うことができる。ただし、一度搬出した荷物が列に戻ることはない。
搬出操作：
現在残っている荷物の列から、その列で連続する 1 個以上の荷物からなる区間を 1 つ選ぶ。ただし、選んだ区間に含まれる荷物の重さの合計は K 以下でなければならない。選んだ区間に含まれる荷物をすべて列から取り除いて搬出する。荷物が取り除かれた後、残った荷物は元の相対的な順序を保ったまま隙間を詰めて再び一列に並ぶ（残った荷物がない場合、列は空になる）。
なお、1 回の搬出操作で選べる区間は 1 つだけであり、また、各回の搬出操作における重さの合計の上限は毎回 K である（過去の操作で搬出した量によらない）。
例えば、荷物が [A_1, A_2, A_3, A_4, A_5] と並んでいるとき、A_2 + A_3 \leq K であれば、最初の搬出操作で A_2 と A_3 をまとめて搬出できる。搬出後、列は [A_1, A_4, A_5] となる。このとき、元の列では隣接していなかった A_1 と A_4 が新たに隣接するため、次の搬出操作で A_1 と A_4 をまとめて 1 つの区間として選ぶことができる（ただし A_1 + A_4 \leq K である場合に限る）。
高橋君ができるだけ多くの荷物を搬出するとき、搬出できる荷物の最大個数を求めよ。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 1 \leq A_i \leq 10^{18}
- 入力はすべて整数である
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、荷物の個数を表す整数 N と、1 回の搬出操作で搬出できる荷物の重さの合計の上限を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各荷物の重さを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
搬出できる荷物の最大個数を 1 行で出力せよ。
入力例 1
5 4 3 1 3 1 3
出力例 1
5
入力例 2
3 2 3 3 3
出力例 2
0
入力例 3
10 10 5 6 3 8 2 7 1 4 9 5
出力例 3
10
入力例 4
20 15 7 3 12 5 8 1 6 14 2 9 4 11 3 7 10 2 13 5 8 6
出力例 4
20
入力例 5
1 1000000000000000000 1000000000000000000
出力例 5
1
Score : 333 pts
Problem Statement
Takahashi is in charge of organizing a warehouse. There are N items of luggage lined up in a row in the warehouse, and the weight of the i-th item from the left is A_i.
Takahashi uses a truck to carry out the luggage. Takahashi can repeat the following carrying-out operation any number of times (including 0 times). Once an item has been carried out, it does not return to the row.
Carrying-out operation:
From the current remaining row of items, choose one contiguous interval consisting of 1 or more consecutive items in that row. However, the total weight of the items in the chosen interval must be at most K. Remove all items in the chosen interval from the row and carry them out. After the items are removed, the remaining items close the gaps while maintaining their original relative order and form a row again (if no items remain, the row becomes empty).
Note that only one interval can be chosen per carrying-out operation, and the upper limit on the total weight for each carrying-out operation is K every time (regardless of the amount carried out in previous operations).
For example, if the items are arranged as [A_1, A_2, A_3, A_4, A_5], and A_2 + A_3 \leq K, then in the first carrying-out operation, A_2 and A_3 can be carried out together. After this, the row becomes [A_1, A_4, A_5]. At this point, A_1 and A_4, which were not adjacent in the original row, are now adjacent, so in the next carrying-out operation, A_1 and A_4 can be selected together as one interval (provided that A_1 + A_4 \leq K).
Find the maximum number of items Takahashi can carry out when he tries to carry out as many items as possible.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 1 \leq A_i \leq 10^{18}
- All input values are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of items and an integer K representing the upper limit on the total weight of items that can be carried out in one operation, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the weight of each item, separated by spaces.
Output
Output the maximum number of items that can be carried out, in one line.
Sample Input 1
5 4 3 1 3 1 3
Sample Output 1
5
Sample Input 2
3 2 3 3 3
Sample Output 2
0
Sample Input 3
10 10 5 6 3 8 2 7 1 4 9 5
Sample Output 3
10
Sample Input 4
20 15 7 3 12 5 8 1 6 14 2 9 4 11 3 7 10 2 13 5 8 6
Sample Output 4
20
Sample Input 5
1 1000000000000000000 1000000000000000000
Sample Output 5
1