#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
ll dp[55][55][55][55]; // thing
ll sum[55][55][55][55]; // thing
ll vals[55][55];
int main() {
fastIO;
int n, m; cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> vals[i][j];
}
}
for(int xsz = 1; xsz <= m; xsz++) {
for(int ysz = 1; ysz <= n; ysz++) {
for(int x = 0; x+xsz-1 < m; x++) {
for(int y = 0; y+ysz-1 < n; y++) {
if(xsz == 1 && ysz == 1) {
dp[x][x][y][y] = 0;
sum[x][x][y][y] = vals[y][x];
} else {
int xr = x + xsz - 1;
int yr = y + ysz - 1;
dp[x][xr][y][yr] = LLONG_MAX;
if(xsz > 1) {
sum[x][xr][y][yr] = sum[x][x][y][yr] + sum[x+1][xr][y][yr];
for(int leftBound = x; leftBound < xr; leftBound++) {
dp[x][xr][y][yr] = min(dp[x][xr][y][yr], dp[x][leftBound][y][yr] + dp[leftBound+1][xr][y][yr] + sum[x][xr][y][yr]);
}
}
if(ysz > 1) {
sum[x][xr][y][yr] = sum[x][xr][y][y] + sum[x][xr][y+1][yr];
for(int leftBound = y; leftBound < yr; leftBound++) {
dp[x][xr][y][yr] = min(dp[x][xr][y][yr], dp[x][xr][y][leftBound] + dp[x][xr][leftBound+1][yr] + sum[x][xr][y][yr]);
}
}
}
// printf("%d %d %d %d: %d, sum was %d\n", x, x+xsz-1, y, y+ysz-1, dp[x][x+xsz-1][y][y+ysz-1], sum[x][x+xsz-1][y][y+ysz-1]);
}
}
}
}
cout << dp[0][m-1][0][n-1];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |