접속 대기열의 한 칸

문제

한 게임 서버는 접속 요청을 대기열에 모아 두었다가 일정한 간격으로 처리한다. 운영자는 대기열의 크기를 제한했을 때 얼마나 많은 요청을 받지 못하는지 확인하려고 한다. 대기열에는 최대 C개의 요청이 들어갈 수 있으며, 관찰을 시작하기 전에는 대기열이 비어 있다. 관찰은 N개의 구간으로 나뉜다. 각 구간에서는 요청 도착과 요청 처리가 반드시 이 순서로 일어난다. 먼저 해당 구간에 도착한 A개의 요청을 대기열에 넣는다. 이때 빈자리보다 많은 요청이 도착하면 빈자리 수만큼만 받아들이고 나머지는 즉시 거절한다. 거절한 요청은 이후 구간에서 다시 도착하지 않는다. 이어서 대기열의 요청을 최대 P개 처리하여 대기열에서 제거한다. 대기 중인 요청이 P개보다 적으면 그 요청을 모두 처리한다. 예를 들어 대기열의 최대 크기가 6이고 한 구간에 최대 4개를 처리한다고 하자. 구간 시작 시 3개가 기다리고 있는데 5개가 도착하면, 새 요청 중 3개를 받아들이고 2개를 거절한다. 그다음 대기열에 있는 6개 중 4개를 처리하므로 구간이 끝났을 때는 2개가 남는다. 각 구간에 도착하는 요청 수가 시간순으로 주어진다. 모든 구간에서 거절한 요청 수의 합과 마지막 구간의 처리가 끝난 직후 대기열에 남은 요청 수를 구해야 한다. 마지막 구간이 끝난 뒤에는 추가 처리를 하지 않는다. 요청의 종류와 처리 순서는 두 결과에 영향을 주지 않으며, 모든 요청은 각각 하나로 센다. 거절한 요청이 없거나 마지막에 남은 요청이 없으면 해당 값은 0이다.

입력

첫째 줄에 정수 N, C, P가 공백으로 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000, 1 ≤ P ≤ 1,000이다.
둘째 줄에 각 구간에 도착한 요청 수를 나타내는 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 0 ≤ A_i ≤ 1,000이며, 입력 순서가 구간의 시간순이다.

출력

거절한 요청 수의 합과 마지막 구간 직후 대기열에 남은 요청 수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다.

3 6 4
5 8 1

3 0

2 3 1
3 3

2 2

1 5 8
0

0 0

출처: Devin.KR 자체 제작