예약금 장부 마감

문제

한 병원의 백엔드 서버는 특정 날짜의 검사 예약을 관리한다. 이 날짜에 동시에 유지할 수 있는 예약은 최대 K개다. 서버는 예약 요청과 취소 요청을 입력에 주어진 순서대로 하나씩 처리하고, 모든 요청을 처리한 뒤 예약금 장부를 마감한다. 처음에는 유지 중인 예약이 없고 장부의 잔액도 0원이다. 예약 요청은 B x p로 주어진다. x는 예약 식별 번호이고 p는 이번 요청의 예약금이다. 현재 x번 예약이 유지 중이지 않고 유지 중인 예약 수가 K보다 작으면 요청을 승인한다. 승인하면 x번 예약과 예약금 p를 저장하고 장부 잔액에 p원을 더한다. 두 조건 중 하나라도 만족하지 않으면 요청을 거절한다. 거절된 요청은 예약 상태와 장부 잔액에 아무 영향도 주지 않으며, 거절 횟수만 1 증가한다. 취소 요청은 C x로 주어진다. x번 예약이 유지 중이면 해당 예약을 제거하고, 그 예약에 저장된 예약금을 p라고 할 때 max(0, p-F)원을 환불하여 장부 잔액에서 뺀다. F는 모든 취소에 공통으로 적용하는 수수료다. 유지 중이지 않은 번호의 취소 요청은 무시하며 거절 횟수에도 포함하지 않는다. 취소된 식별 번호로 나중에 다시 예약할 수 있다. 이때 새로운 요청의 예약금을 저장하며 과거 예약금은 사용하지 않는다. 예약을 승인한 뒤 취소하더라도 앞서 기록한 거절 횟수는 바뀌지 않는다. 같은 번호의 요청이 연속해서 들어올 수도 있으며, 각 요청은 직전 요청까지 처리한 상태를 기준으로 판단한다. 모든 요청을 처리한 뒤 유지 중인 예약 수, 장부 잔액, 거절된 예약 요청 수를 구한다. 장부 잔액에는 유지 중인 예약의 예약금과 이미 취소된 예약에서 남은 수수료가 함께 포함된다.

입력

첫 줄에 요청 수 N, 예약 한도 K, 취소 수수료 F가 공백으로 주어진다. 1≤N≤20,000, 1≤K≤20,000, 0≤F≤1,000,000이다.
다음 N개 줄에는 B x p 또는 C x 형식의 요청이 하나씩 주어진다. 1≤x≤100,000, 1≤p≤1,000,000이다. 모든 수는 정수다.

출력

유지 중인 예약 수, 장부 잔액, 거절된 예약 요청 수를 순서대로 한 줄에 공백으로 구분하여 출력한다. 유지 중인 예약이 없으면 첫 번째 값으로 0을 출력한다.

7 2 30
B 1 100
B 2 20
B 3 70
C 1
B 3 70
C 2
B 3 90

1 120 2

4 1 0
C 9
B 9 50
C 9
C 9

0 0 0

출처: Devin.KR 자체 제작