#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL n, m, dp[58][58][58][58], sub[58][58];
LL dodaj(int px, int py, int cx, int cy){
int d1 = 0, d2 = 0, d3 = 0;
if (px >= 0 and py >= 0) d1 = sub[px][py];
if (px >= 0) d2 = sub[px][cy];
if (py >= 0) d3 = sub[cx][py];
return d1 + sub[cx][cy] - d2 - d3;
}
LL reks(int px, int py, int cx, int cy){
LL suma = dodaj(px-1, py-1, cx-1, cy-1), res = 1000000009;
if (px+1 == cx and py+1 == cy) return dp[px][py][cx][cy];
else if (dp[px][py][cx][cy] >= suma) return dp[px][py][cx][cy];
// cout << suma << " -> " << px << " " << py << " " << cx << " " << cy << endl;
for(int i=px+1; i < cx; i++) res = min(res, reks(px, py, i, cy) + reks(i, py, cx, cy) + suma);
for(int i=py+1; i < cy; i++) res = min(res, reks(px, py, cx, i) + reks(px, i, cx, cy) + suma);
// cout << px << " " << py << " | " << cx << " " << cy << " | " << res << endl;
return dp[px][py][cx][cy] = res;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m;
for(int i1=0; i1 < 58; i1++) for(int i2=0; i2 < 58; i2++) for(int i3=0; i3 < 58; i3++) for(int i4=0; i4 < 58; i4++) dp[i1][i2][i3][i4] = -1;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> dp[i][j][i+1][j+1];
if (i == 0 and j == 0) sub[0][0] = dp[0][0][1][1];
else if (i == 0) sub[0][j] = sub[0][j-1] + dp[0][j][1][j+1];
else if (j == 0) sub[i][0] = sub[i-1][0] + dp[i][0][i+1][1];
else sub[i][j] = sub[i][j-1] + sub[i-1][j] - sub[i-1][j-1] + dp[i][j][i+1][j+1];
}
}
cout << reks(0, 0, n, m)-sub[n-1][m-1]; return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
30 ms |
88788 KB |
Output is correct |
| 2 |
Correct |
28 ms |
88888 KB |
Output is correct |
| 3 |
Correct |
27 ms |
88880 KB |
Output is correct |
| 4 |
Correct |
28 ms |
88772 KB |
Output is correct |
| 5 |
Correct |
28 ms |
88916 KB |
Output is correct |
| 6 |
Correct |
28 ms |
88888 KB |
Output is correct |
| 7 |
Correct |
30 ms |
88916 KB |
Output is correct |
| 8 |
Correct |
48 ms |
88916 KB |
Output is correct |
| 9 |
Correct |
45 ms |
88780 KB |
Output is correct |
| 10 |
Correct |
53 ms |
88912 KB |
Output is correct |
| 11 |
Correct |
50 ms |
88820 KB |
Output is correct |
| 12 |
Correct |
111 ms |
88908 KB |
Output is correct |
| 13 |
Correct |
153 ms |
88916 KB |
Output is correct |
| 14 |
Correct |
79 ms |
88896 KB |
Output is correct |
| 15 |
Correct |
201 ms |
88924 KB |
Output is correct |
| 16 |
Correct |
44 ms |
88860 KB |
Output is correct |
| 17 |
Correct |
94 ms |
88888 KB |
Output is correct |
| 18 |
Correct |
520 ms |
88928 KB |
Output is correct |
| 19 |
Correct |
815 ms |
88932 KB |
Output is correct |
| 20 |
Correct |
944 ms |
88932 KB |
Output is correct |
