#include <bits/stdc++.h>
using namespace std;
static constexpr int N = 50;
int main() {
int n; cin >> n;
int m; cin >> m;
int r[N][N]{};
for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> r[i][j];
for (int i = 1; i < n; ++i) for (int j = 0; j < m; ++j) r[i][j] += r[i-1][j];
for (int i = 0; i < n; ++i) for (int j = 1; j < m; ++j) r[i][j] += r[i][j-1];
auto sum = [&](int il, int ih, int jl, int jh) -> int {
int ans = r[ih][jh];
if (il) ans -= r[il-1][jh];
if (jl) ans -= r[ih][jl-1];
if (il && jl) ans += r[il-1][jl-1];
return ans;
};
int dp[N][N][N][N]{};
bool vis[N][N][N][N]{};
auto solve = [&](auto&& self, int i0, int i1, int j0, int j1) -> int {
if (i0 == i1 && j0 == j1) return 0;
if (vis[i0][i1][j0][j1]) return dp[i0][i1][j0][j1];
vis[i0][i1][j0][j1] = true;
int mn = 1e9;
for (int k = 1; k <= i1-i0; ++k) {
mn = min(mn, self(self, i0, i0+k-1, j0, j1) + self(self, i0+k, i1, j0, j1));
}
for (int k = 1; k <= j1-j0; ++k) {
mn = min(mn, self(self, i0, i1, j0, j0+k-1) + self(self, i0, i1, j0+k, j1));
}
return dp[i0][i1][j0][j1] = mn + sum(i0, i1, j0, j1);
};
cout << solve(solve, 0, n-1, 0, m-1) << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
30784 KB |
Output is correct |
2 |
Correct |
17 ms |
30804 KB |
Output is correct |
3 |
Correct |
16 ms |
30804 KB |
Output is correct |
4 |
Correct |
17 ms |
30832 KB |
Output is correct |
5 |
Correct |
16 ms |
30860 KB |
Output is correct |
6 |
Correct |
16 ms |
30880 KB |
Output is correct |
7 |
Correct |
17 ms |
30884 KB |
Output is correct |
8 |
Correct |
23 ms |
30832 KB |
Output is correct |
9 |
Correct |
30 ms |
30872 KB |
Output is correct |
10 |
Correct |
37 ms |
30836 KB |
Output is correct |
11 |
Correct |
35 ms |
30872 KB |
Output is correct |
12 |
Correct |
84 ms |
30936 KB |
Output is correct |
13 |
Correct |
125 ms |
30888 KB |
Output is correct |
14 |
Correct |
46 ms |
30804 KB |
Output is correct |
15 |
Correct |
156 ms |
30884 KB |
Output is correct |
16 |
Correct |
27 ms |
30804 KB |
Output is correct |
17 |
Correct |
71 ms |
30872 KB |
Output is correct |
18 |
Correct |
386 ms |
30872 KB |
Output is correct |
19 |
Correct |
622 ms |
30880 KB |
Output is correct |
20 |
Correct |
750 ms |
30880 KB |
Output is correct |