27208번 - Melons 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 85 | 48 | 41 | 58.571% |
문제
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 ≤ i ≤ N$) is $A_i$.
Rie is working at EGOI Farm. Her job is packing melons into boxes. Now, an integer $x$ ($1 ≤ x ≤ N$) is determined in EGOI Farm. After that, she will receive the melons $x, x + 1, \dots , 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$.
입력
Read the following data from the standard input. Given values are all integers.
$N$ $L$
$A_1$
$A_2$
$\vdots$
$A_N$
출력
Write $N$ lines to the standard output. The $i$-th line ($1 ≤ i ≤ 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.
제한
- $1 ≤ N ≤ 200\,000$.
- $1 ≤ L ≤ 1\,000\,000\,000 (= 10^9)$.
- $1 ≤ A_i ≤ L$ ($1 ≤ i ≤ N$).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $A_1 = A_2 = \cdots = A_N$. |
| 2 | 21 | $N ≤ 1\,000$. |
| 3 | 29 | For every $x$, the number of boxes shipped by Rie will be less than or equal to $10$. |
| 4 | 33 | For every $x$, Rie will put at most $10$ melons into a box. |
| 5 | 11 | No additional constraints. |
예제 입력 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
For example, if $x = 1$, Rie will pack melons into boxes as follows.
- 1. 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.
예제 입력 2
6 160 63 63 63 63 63 63
예제 출력 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.
예제 입력 3
5 20 7 10 4 6 8
예제 출력 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.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호