/
実行時間制限: 1.5 sec / メモリ制限: 512 MiB
Score: 100 points
Problem Statement
In EGOI Farm, the employees are receiving and shipping melons. This morning, N melons are received. The melons are numbered from 1 to N. The weight of melon i (1 \le i \le N) is A_{i}.
Rie is working at EGOI Farm. Her job is packing melons into boxes. Now, an integer x (1 \le x \le N) is determined in EGOI Farm. After that, she will receive the melons x, x + 1, \ldots, N, in this order. She will pack them into boxes by repeating the following process.
- Rie will take an empty box. She will repeat putting the melons into the box. However, if the total weight of the melons in the box will exceeds L after putting the next melon into the box, she will not put it into the box. Then, she will ship the box. (In this case, she will put the next melon into a new box.) After putting the melon N into a box, she will ship the box, and her job will be finished.
Rie wants to prepare for her job for all possible values of x. Write a program which, given information of the melons and the maximum possible weight L of a box, calculates the number of boxes shipped by her and the total weight of the melons in the last box for all possible values of x.
Input
Read the following data from the standard input. Given values are all integers.
N L
A_{1}
A_{2}
\vdots
A_{N}
Output
Write N lines to the standard output. The i-th line (1 \le i \le N) of output corresponds to the case x = i. This line should contain the number of shipped boxes and the total weight of the melons in the last box if x = i. These two values should be separated by a space.
Constraints
- 1 \le N \le 200\,000.
- 1 \le L \le 1\,000\,000\,000 (= 10^{9}).
- 1 \le A_{i} \le L (1 \le i \le N).
Subtasks
- (6 points) A_{1} = A_{2} = \cdots = A_{N}.
- (21 points) N \le 1\,000.
- (29 points) For every x, the number of boxes shipped by Rie will be less than or equal to 10.
- (33 points) For every x, Rie will put at most 10 melons into a box.
- (11 points) No additional constraints.
Sample Input 1
7 100 20 80 50 40 20 80 10
Sample Output 1
4 10 4 10 3 10 2 90 2 10 1 90 1 10
For example, if x = 1, Rie will pack melons into boxes as follows.
- Rie puts the melon 1 into a box. The total weight of the box is 20.
- Rie puts the melon 2 into the same box. The total weight of the box is 100.
- If Rie puts the melon 3 into the same box, the total weight of the box will be 150. Therefore, Rie ships the current box, and puts the melon 3 into a new box. The total weight of the new box is 50.
- Rie puts the melon 4 into the box. The total weight of the box is 90.
- If Rie puts the melon 5 into the box, the total weight of the box will be 110. Therefore, Rie ships the current box, and puts the melon 5 into a new box. The total weight of the new box is 20.
- Rie puts the melon 6 into the box. The total weight of the box is 100.
- If Rie puts the melon 7 into the box, the total weight of the box will be 110. Therefore, Rie ships the current box, and puts the melon 7 into a new box. The total weight of the new box is 10.
- Finally, Rie ships the current box.
If x = 1, Rie ships 4 boxes, and the total weight of the melons in the last box is 10. Therefore, output 4 and 10 in this order. These two values should be separated by a space.
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5.
Sample Input 2
6 160 63 63 63 63 63 63
Sample Output 2
3 126 3 63 2 126 2 63 1 126 1 63
For example, if x = 1, Rie puts the melons 1, 2 into the first box, the melons 3, 4 into the second box, and the melons 5, 6 into the third box. Rie ships 3 boxes, and the total weight of the melons in the last box is 126. Therefore, output 3 and 126 in the first line in this order. These two values should be separated by a space.
This sample input satisfies the constraints of all the subtasks.
Sample Input 3
5 20 7 10 4 6 8
Sample Output 3
2 18 2 8 1 18 1 14 1 8
For example, if x = 2, Rie puts the melons 2, 3, 4 into the first box. Rie puts only the melon 5 into the second box. Rie ships 2 boxes, and the total weight of the melons in the last box is 8. Therefore, output 2 and 8 in the second line in this order. These two values should be separated by a space.
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5.
配点 : 100 点
問題文
EGOI 農場はメロンの入荷と出荷を行っており,今朝 N 個のメロンを入荷した.メロンには入荷した順に 1 から N までの番号が付けられており,メロン i (1 \leqq i \leqq N) の重さは A_{i} である.
EGOI 農場で働く理恵さんは,メロンの箱詰めを担当している.今から,EGOI 農場で整数 x (1 \leqq x \leqq N) が決定される.その後,理恵さんにはメロン x, x + 1, \ldots, N がこの順に渡され,以下を繰り返して箱詰めを行うことになっている.
- 空の箱を用意し,その箱に渡されたメロンを入れ続ける.ただし,渡されたメロンを入れたらその箱に入っているメロンの重さの合計が L を超えてしまう場合は,そのメロンを入れずに箱を出荷する. (そのメロンは次の箱に入れることになる.)メロン N を箱に入れたら,その箱を出荷して理恵さんの作業は終了する.
理恵さんは x がどの値に決定されても大丈夫なように準備をしたいと思った.入荷するメロンの情報と箱の重量制限 L が与えられるので,すべての x の場合について,出荷する箱の個数と,最後に出荷する箱に入れるメロンの重さの合計を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N L
A_{1}
A_{2}
\vdots
A_{N}
出力
標準出力に N 行で出力せよ.i 行目 (1 \leqq i \leqq N) には,x = i の場合について,出荷する箱の個数と最後に出荷する箱に入れるメロンの重さの合計をこの順に空白区切りで出力せよ.
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq L \leqq 1\,000\,000\,000 (= 10^{9}).
- 1 \leqq A_{i} \leqq L (1 \leqq i \leqq N).
小課題
- (6 点) A_{1} = A_{2} = \cdots = A_{N}.
- (21 点) N \leqq 1\,000.
- (29 点) どの x に対しても,理恵さんが出荷する箱の数は 10 個以下になる.
- (33 点) どの x に対しても,理恵さんが 1 つの箱に入れるメロンの個数は 10 個以下になる.
- (11 点) 追加の制約はない.
入力例 1
7 100 20 80 50 40 20 80 10
出力例 1
4 10 4 10 3 10 2 90 2 10 1 90 1 10
例えば x = 1 の場合,理恵さんは以下のように箱詰めを行うことになる.
- メロン 1 を箱に入れる.箱のメロンの重さの合計は 20 となる.
- メロン 2 を箱に入れる.箱のメロンの重さの合計は 100 となる.
- もしメロン 3 を箱に入れたら,箱のメロンの重さの合計は 150 となってしまう.そのため,現在の箱を出荷し,メロン 3 は新しい箱に入れる.新しい箱のメロンの重さの合計は 50 となる.
- メロン 4 を箱に入れる.箱のメロンの重さの合計は 90 となる.
- もしメロン 5 を箱に入れたら,箱のメロンの重さの合計は 110 となってしまう.そのため,現在の箱を出荷し,メロン 5 は新しい箱に入れる.新しい箱のメロンの重さの合計は 20 となる.
- メロン 6 を箱に入れる.箱のメロンの重さの合計は 100 となる.
- もしメロン 7 を箱に入れたら,箱のメロンの重さの合計は 110 となってしまう.そのため,現在の箱を出荷し,メロン 7 は新しい箱に入れる.新しい箱のメロンの重さの合計は 10 となる.
- 最後に現在の箱を出荷する.
そのため,x = 1 の場合,出荷する箱の個数は 4 個であり,最後の箱に入れるメロンの重さの合計は 10 となる.したがって,1 行目には 4 と 10 をこの順に空白区切りで出力する.
この入力例は小課題 2, 3, 4, 5 の制約を満たす.
入力例 2
6 160 63 63 63 63 63 63
出力例 2
3 126 3 63 2 126 2 63 1 126 1 63
例えば x = 1 の場合,最初の箱にはメロン 1, 2 を入れ,次の箱にはメロン 3, 4 を入れ,その次の箱にはメロン 5, 6 を入れることになる.そのため,出荷する箱の個数は 3 個であり,最後に出荷する箱に入れるメロンの重さの合計は 126 となる.したがって,1 行目には 3 と 126 をこの順に空白区切りで出力する.
この入力例はすべての小課題の制約を満たす.
入力例 3
5 20 7 10 4 6 8
出力例 3
2 18 2 8 1 18 1 14 1 8
例えば x = 2 の場合,最初の箱にはメロン 2, 3, 4 を入れ,次の箱にはメロン 5 のみを入れることになる.そのため,出荷する箱の個数は 2 個であり,最後に出荷する箱に入れるメロンの重さの合計は 8 となる.したがって,2 行目には 2 と 8 をこの順に空白区切りで出力する.
この入力例は小課題 2, 3, 4, 5 の制約を満たす.