페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8147
서브태스크

고양이 우유 교환 1s 1024MB

문제

Richard의 N마리 고양이 (1 \leq N \leq 5 \cdot 10^5)가 원형으로 줄 서 있다. i번째 고양이는 용량이 a_i​ (1 \leq a_i \leq 10^9) 리터인 버킷을 가지고 있으며, 모든 버킷은 처음에 가득 차 있다.

매 분마다 i번째 고양이는 1 \leq i < N일 때 자신이 가진 모든 우유를 i+1번째 고양이에게 전달하고, N번째 고양이는 1번째 고양이에게 우유를 전달한다. 모든 교환은 동시에 이루어진다(예: 한 고양이가 우유를 x 리터 보내고 x 리터를 받으면, 우유의 양은 변하지 않는다). 만약 어떤 고양이의 총 우유 양이 버킷 용량 a_i​를 초과하면, 초과된 우유는 손실된다.

각 1, 2, \dots, N분 후에 남아 있는 모든 고양이의 우유 총량을 계산하라.


입력

첫 번째 줄에 N이 주어진다.
두 번째 줄에는 정수 a_1, a_2, \dots, a_N​이 주어진다.


출력

N줄을 출력하며, i-번째 줄에는 i분 후에 모든 고양이의 우유 총량을 출력한다.


부분문제

번호 점수 조건
#125점

N \le 2000

#225점

a_i \le 2

#325점

모든 a_i는 [1, 10^9] 범위에서 무작위로 균일하게 생성됨

#425점

추가 제약 조건 없음


예제 #1

6
2 2 2 1 2 1
8
7
6
6
6
6

0분 뒤: [2, 2, 2, 1, 2, 1].

1분 뒤, [1, 2, 2, 1, 1, 1].

2분 뒤, [1, 1, 2, 1, 1, 1]

3분 뒤, [1, 1, 1, 1, 1, 1]

4분 뒤, [1, 1, 1, 1, 1, 1]

5분 뒤, [1, 1, 1, 1, 1, 1]

6분 뒤, [1, 1, 1, 1, 1, 1]


예제 #2

8
3 8 6 4 8 3 8 1
25
20
17
14
12
10
8
8

1분 뒤 각 우유량은 [1, 3, 6, 4, 4, 3, 3, 1]이다.


예제 #3

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000
2000000053
1000000054
56
49
42
35
28
24
20
20

출처

USACO 2024 February Gold 2번

로그인해야 코드를 작성할 수 있어요.