| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 62 | 18 | 15 | 51.724% |
ibasic은 디미고의 부지인 광덕산이 마음에 들지 않아 새로운 산을 그리기로 했다.
ibasic이 그린 산은 $2$차원 평면 위의 $N+1$개의 점 $(0, h_0), (1, h_1), \ldots, (N, h_N)$으로 표현할 수 있다. 모든 $h_i$는 음이 아닌 정수이며 $h_0 = h_N = 0$이다.
ibasic은 자신이 그린 산을 아름다운 강산으로 만들고자 한다. 아름다운 강산은 $1 \le i \le N$인 모든 $i$에 대해 $|h_i - h_{i-1}| = 1$인 산이다.
ibasic은 자신이 그린 산을 아름다운 강산으로 만들기 위해 그림을 다음과 같이 수정할 수 있다.
그림을 수정하다가 그림이 망가지면 안 되기 때문에 그림을 수정한 뒤에도 모든 $h_i$는 $0$ 이상이어야 한다.
그림을 수정하는 것은 상당히 귀찮은 작업이므로 ibasic은 그림을 최소한으로 수정하기로 했다. ibasic이 그린 산을 아름다운 강산으로 만들기 위해 그림을 최소 몇 번 수정해야 하는지 구하시오.
첫 번째 줄에 정수 $N$이 주어진다. $(2\le N\le 10^6)$
두 번째 줄에 산을 나타내는 $N+1$개의 정수 $h_0, h_1, \ldots, h_N$이 공백으로 구분되어 주어진다. $(0 \le h_i \le 10^9;$ $h_0 = h_N = 0)$
첫 번째 줄에 ibasic이 그린 산을 아름다운 강산으로 만들기 위해 필요한 최소 수정 횟수를 출력한다. 단, 수정을 어떻게 해도 ibasic이 그린 산을 아름다운 강산으로 만들 수 없다면 -1을 대신 출력한다.
4 0 3 2 4 0
3
5 0 3 2 5 9 0
-1
School > 한국디지털미디어고등학교 > 제4회 디미고 프로그래밍 챌린지 N번