문제
걸그룹 여자친구에는 N명의 멤버가 있다. 편의상 각 멤버를 1번에서 N번까지의 번호로 부르자.
장태환은 여자친구 멤버들의 키를 알아내고자 한다.
장태환은 여자친구가 진행하는 컨텐츠에서 각 멤버가 다음과 같이 말한 것를 들었다.
"나(i번째 멤버)는 A[i]번째 멤버보다 키가 크거나 같다"
단 여기서 A[i]=i일 수도 있다.
이후 장태환은 i번 원소가 i번 멤버의 위키 페이지에 적혀 있는 키인 배열 H[i]를 얻었다.
그러나 H[i]는 정확하지 않을 수 있고, 장태환은 여자친구가 진행하는 컨텐츠에서 말한 내용을 믿으므로 이에 맞게 위키를 수정하고자 한다.
C[i]초를 사용하면, i번 멤버의 위키 페이지에 적혀 있는 키를 어떤 정수로도 수정할 수 있다.
여자친구가 진행하는 컨텐츠의 내용과 모순이 없도록 위키 페이지에 적혀 있는 키를 수정하는 최소 시간을 구하여라.
입력
첫째 줄에 N이 주어진다. (2<=N<=200'000)
둘째 줄부터 N개의 줄에 걸쳐 A[i], H[i], C[i]가 주어진다.
출력
위키 페이지에 적혀 있는 키를 수정하는 최소 시간을 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 14점 | N<=5000, A[1]=1, A[i]<i(i>=2) |
| #2 | 65점 | A[1]=1, A[i]<i(i>=2) |
| #3 | 21점 | 추가 조건이 없다. |
예제 #1
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
14
장태환이 다음과 같은 방식으로 목록에 있는 여자친구 멤버들의 키를 변경한다.
멤버 1의 키를 6에서 1로 변경한다. 비용은 5이다.
멤버 3의 키를 8에서 4로 변경한다. 비용은 4이다.
멤버 5의 키를 2에서 1,000,000,000으로 변경한다. 비용은 5이다.
그러면 총 비용은 5 + 4 + 5 = 14 이다.
가능한 최소값이므로 출력은 14 이다.
예제 #2
6
4 173 19951207
5 168 19960819
3 163 19970530
2 169 19971004
6 167 19980603
3 164 19980819
0
여자친구의 나무위키 프로필을 이용해 만들어진 예제이다.
예제 #3
20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771
2711043927
예제 #4
20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030
4012295156
로그인해야 코드를 작성할 수 있어요.