| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 181 | 51 | 42 | 31.818% |
유민이의 쿠키 공장에 $N$개의 회사로부터 수주가 들어왔다. $i$번째 회사에는 총 $c_i$박스의 쿠키를 공급해야 하며, $s_i$일차부터 쿠키 납품을 시작할 수 있다.
공장에서는 $x$일차에 다음 두 행동 중 하나를 선택한다.
쿠키를 미리 만들어서 다른 날에 공급할 수 없고, 만든 쿠키는 반드시 당일에 공급해야 함에 유의하라. 모든 회사에 쿠키 납품을 완료하기 위해 마지막으로 쿠키를 만드는 것은 최소 몇 일차가 되는지를 계산해 주자.
또한, 쿠키 산업은 워낙 한 치 앞도 내다볼 수 없기 때문에 $Q$건의 수주 조건 수정 요청이 들어왔다. $j$번째 수정 요청에서는 $q_j$번째 회사에 공급할 쿠키를 $c'_j$박스로, 공급 시작 일차를 $s'_j$일차로 수정한다. 각 수정 요청은 이후의 수정 요청들을 처리할 때도 초기화되지 않고 영향을 미침에 유의하라. 시작 상태와 각 수정 요청 이후에 대해 문제를 해결해 보자.
첫 번째 줄에 정수 $N$이 주어진다.
다음 $N$개의 줄 중 $i$번째 줄에 두 개의 정수 $c_i$, $s_i$가 공백으로 구분되어 주어진다.
다음 줄에 정수 $Q$가 주어진다.
다음 $Q$개의 줄 중 $j$번째 줄에 세 개의 정수 $q_j$, $c'_j$, $s'_j$가 공백으로 구분되어 주어진다.
첫 번째 줄에 시작 상태에서의 문제의 정답을 출력한다.
다음 $Q$개의 줄 중 $j$번째 줄에 $j$번째 수정 요청을 처리한 후의 문제의 정답을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $N, Q \leq 2500$ |
| 2 | 54 | $s_i$는 수정되지 않음. 즉, 항상 $s_i = s'_{q_j}$ |
| 3 | 39 | 추가 제약 조건 없음 |
1 1 1 1 1 2 1
1 2
5 3 1 6 5 6 2 100 1 3 4 5 4 2 1 2 2 5 3 4 2 1 10 1 5 2 4
118 20 16 14 21 20
수정 요청 전후의 상태가 같을 수도 있음에 유의하라. 즉, $c'_j=c_{q_j};$ $s'_j=s_{q_j}$일 수도 있다.
School > 한국과학영재학교 > 2025 KSA Automata Winter Contest H번