#include <bits/stdc++.h>
#define DIM 52
#define INF 2000000000
using namespace std;
int sp[DIM][DIM],a[DIM][DIM],opt[DIM][DIM][DIM][DIM];
int n,m,i,j;
int solve (int x, int y, int x2, int y2){
if (x == x2 && y == y2)
return 0;
if (opt[x][y][x2][y2]) /// am mai calculat deja starea asta
return opt[x][y][x2][y2];
int sol = INF;
for (int i=y;i<y2;i++)
sol = min (sol,solve(x,y,x2,i) + solve(x,i+1,x2,y2));
for (int i=x;i<x2;i++)
sol = min (sol,solve(x,y,i,y2) + solve(i+1,y,x2,y2));
opt[x][y][x2][y2] = sol + sp[x2][y2] - sp[x2][y-1] - sp[x-1][y2] + sp[x-1][y-1];
return opt[x][y][x2][y2];
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
cin>>a[i][j];
sp[i][j] = sp[i-1][j] + sp[i][j-1] - sp[i-1][j-1] + a[i][j];
}
cout<<solve (1,1,n,m);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
896 KB |
Output is correct |
7 |
Correct |
5 ms |
1024 KB |
Output is correct |
8 |
Correct |
14 ms |
2688 KB |
Output is correct |
9 |
Correct |
19 ms |
3712 KB |
Output is correct |
10 |
Correct |
27 ms |
4352 KB |
Output is correct |
11 |
Correct |
23 ms |
3840 KB |
Output is correct |
12 |
Correct |
76 ms |
7424 KB |
Output is correct |
13 |
Correct |
119 ms |
9592 KB |
Output is correct |
14 |
Correct |
36 ms |
4732 KB |
Output is correct |
15 |
Correct |
145 ms |
10616 KB |
Output is correct |
16 |
Correct |
17 ms |
3712 KB |
Output is correct |
17 |
Correct |
57 ms |
7424 KB |
Output is correct |
18 |
Correct |
379 ms |
16632 KB |
Output is correct |
19 |
Correct |
647 ms |
20064 KB |
Output is correct |
20 |
Correct |
817 ms |
21624 KB |
Output is correct |