묶음 단위 생산 정산

문제

한 공장의 생산 라인에서는 완성된 부품을 창고에 넣고, 주문이 들어오면 창고에서 부품을 꺼내 출고한다. 백엔드 담당자는 생산, 주문, 정산이 섞인 작업 기록을 입력된 순서대로 처리해야 한다. 모든 부품은 같은 종류이며, 작업을 시작할 때 창고 재고와 정산 대기 수량, 누적 정산액, 거절한 주문 수는 모두 0이다. 각 기록은 정수 x 하나로 주어진다. x가 양수이면 부품 x개가 생산된 것이므로 창고 재고에 x를 더한다. x가 음수이면 부품 -x개를 요구하는 주문이다. 현재 재고가 요구 수량 이상이면 주문을 전부 출고하여 재고에서 요구 수량을 빼고, 정산 대기 수량에 같은 수량을 더한다. 재고가 부족하면 주문 전체를 거절하고 거절한 주문 수를 1 늘린다. 거절한 주문은 나중에 다시 처리하지 않으며 재고와 정산 대기 수량에도 영향을 주지 않는다. 재고와 요구 수량이 같을 때에는 정상적으로 출고한다. x가 0이면 정산을 실행한다. 출고한 부품은 K개를 한 묶음으로 하여 정산하며, 한 묶음의 정산액은 P이다. 정산 대기 수량에서 만들 수 있는 완전한 묶음을 모두 정산하여 그 금액을 누적 정산액에 더한다. 정산한 부품은 정산 대기 수량에서 제외하고, K개보다 적게 남은 부품은 다음 정산까지 유지한다. 정산은 창고 재고를 바꾸지 않으며, 완전한 묶음이 없으면 아무 변화도 없다. 모든 기록의 처리가 끝나도 추가 정산을 실행하지 않는다. 따라서 마지막 정산 이후 출고한 부품이 있다면 최종 정산 대기 수량이 K 이상일 수도 있다. 최종 창고 재고, 정산 대기 수량, 누적 정산액, 거절한 주문 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 기록 수 N, 정산 묶음의 크기 K, 한 묶음의 정산액 P가 공백으로 구분되어 주어진다. N, K, P는 정수이며 1≤N≤100,000, 1≤K≤100,000, 1≤P≤1,000,000이다.
다음 N개의 줄에는 작업 기록을 나타내는 정수 x가 한 줄에 하나씩 주어진다. 각 기록은 -9≤x≤9를 만족한다.

출력

최종 창고 재고, 정산 대기 수량, 누적 정산액, 거절한 주문 수를 이 순서대로 공백으로 구분하여 한 줄에 출력한다. 각 값은 정수로 출력하며, 해당 수량이나 금액이 없으면 0을 출력한다.

10 4 30
5
-3
-4
0
6
-5
0
-2
0
1

2 2 60 1

6 1 9
-1
0
1
-1
0
0

0 0 9 1

출처: Devin.KR 자체 제작