| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 1024 MB | 223 | 71 | 42 | 40.777% |
커플이 된 록금이는 $N$일간의 데이트 약속을 잡기로 했다!
록금이 커플은 연속으로 데이트할수록 하루에 얻을 수 있는 애정이 점점 늘어난다. 구체적으로 연속 1ドル$일차에는 1ドル,ドル 연속 2ドル$일차에는 2ドル,ドル $\cdots,ドル 연속 $i$일차에는 $i$만큼의 애정을 얻을 수 있다. 즉 3ドル$일 연속으로 데이트한다면 1ドル + 2 + 3 = 6$의 애정을 얻는다.
솔로였던 쿠민이는 커플이 된 록금이가 보기 싫었다. 그래서 쿠민이는 $X_1, X_2, \cdots, X_M$일에 저주를 걸어, 록금이 커플이 $X_j$일차에 데이트한다면 록금이 커플의 애정이 $Y_j$만큼 깎이도록 만들었다. 저주 걸린 날에 데이트하더라도 연속 $i$일차에 $i$만큼의 애정을 얻을 수 있다는 사실에는 변함이 없다. 안타깝게도, 저주로 인해 특정 날짜까지의 누적 애정 총합이 음수가 될 수 있다.
쿠민이의 괘씸한 계획을 알게 된 록금이는 애정을 최대로 얻기 위한 데이트 약속을 다시 잡기로 했다. 록금이를 도와 $N$일간의 데이트를 끝마쳤을 때, 록금이 커플이 최대로 얻을 수 있는 애정의 총합을 구해보자.
첫째 줄에 데이트 일정을 짤 날짜의 수 $N,ドル 저주에 걸린 날짜의 수 $M$이 공백으로 구분되어 주어진다.
둘째 줄부터 $M$개의 줄에 걸쳐, $j+1$번째 줄에 저주에 걸린 날짜 $X_j,ドル 깎이는 애정량 $Y_j$가 공백으로 구분되어 주어진다.
$(X_j,\ Y_j)$는 $X_j$에 대해 오름차순으로 주어지며, 모든 $X_j$는 서로 다르다.
록금이 커플이 최대로 얻을 수 있는 애정의 총합을 출력한다.
입력으로 주어지는 수는 모두 정수이다.
3 1 2 2
4
3 2 2 2 3 2
2
10 3 2 1 3 10 7 10
34
10 10 1 1 2 2 3 3 4 4 5 4 6 6 7 7 8 8 9 9 10 10
1
720 4 118 1110 313 704 411 525 621 6894
250327
University > 국민대학교 > 2025 KPSC Summer Algorithm Challenge F번