#include <stdio.h>
#include <algorithm>
int N,p; long long A[2][2222],D[2][2222];
int main()
{
scanf ("%d",&N);
for (int i=0;i<N;i++){
for (int j=0;j<N;j++){
scanf ("%lld",&A[p][j]);
if (i == 0 && j == 0) D[p][j] = 0;
else D[p][j] = 1000000000000000ll;
if (i != 0){
int a = (A[!p][j] > A[p][j]) ? 0 : A[p][j] - A[!p][j] + 1;
if (D[p][j] > D[!p][j] + a)
D[p][j] = D[!p][j] + a;
}
if (j != 0){
int a = (A[p][j-1] > A[p][j]) ? 0 : A[p][j] - A[p][j-1] + 1;
if (D[p][j] > D[p][j-1] + a)
D[p][j] = D[p][j-1] + a;
}
}
p = !p;
}
printf ("%d\n",D[!p][N-1]);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1156 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1156 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1156 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
1156 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1156 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1156 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1156 KB |
Output is correct |
| 6 |
Correct |
8 ms |
1156 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1156 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1156 KB |
Output is correct |
| 15 |
Correct |
8 ms |
1156 KB |
Output is correct |
| 16 |
Correct |
8 ms |
1156 KB |
Output is correct |
| 17 |
Correct |
4 ms |
1156 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
672 ms |
1156 KB |
Output is correct |
| 2 |
Correct |
640 ms |
1156 KB |
Output is correct |
| 3 |
Correct |
680 ms |
1156 KB |
Output is correct |
| 4 |
Correct |
688 ms |
1156 KB |
Output is correct |
| 5 |
Correct |
564 ms |
1156 KB |
Output is correct |
| 6 |
Correct |
640 ms |
1156 KB |
Output is correct |
| 7 |
Correct |
676 ms |
1156 KB |
Output is correct |
| 8 |
Correct |
684 ms |
1156 KB |
Output is correct |
| 9 |
Correct |
704 ms |
1156 KB |
Output is correct |
| 10 |
Correct |
632 ms |
1156 KB |
Output is correct |
| 11 |
Correct |
588 ms |
1156 KB |
Output is correct |
| 12 |
Correct |
576 ms |
1156 KB |
Output is correct |
| 13 |
Correct |
516 ms |
1156 KB |
Output is correct |
| 14 |
Correct |
604 ms |
1156 KB |
Output is correct |
| 15 |
Correct |
504 ms |
1156 KB |
Output is correct |
| 16 |
Correct |
604 ms |
1156 KB |
Output is correct |
| 17 |
Correct |
600 ms |
1156 KB |
Output is correct |
| 18 |
Correct |
580 ms |
1156 KB |
Output is correct |
| 19 |
Correct |
608 ms |
1156 KB |
Output is correct |
| 20 |
Correct |
632 ms |
1156 KB |
Output is correct |
| 21 |
Correct |
544 ms |
1156 KB |
Output is correct |
