#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;
//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007
typedef long long ll;
ll add(ll a, ll b) {
a += b;
if(a >= MOD) {
a -= MOD;
}
return a;
}
ll sub(ll a, ll b) {
a -= b;
if(a < 0) {
a += MOD;
}
return a;
}
ll mul(ll a, ll b) {
return (a * b)%MOD;
}
void add_self(ll& a, ll b) {
a = add(a, b);
}
void sub_self(ll& a, ll b) {
a = sub(a, b);
}
void mul_self(ll& a, ll b) {
a = mul(a, b);
}
const ll MAXN = 51;
ll pref[MAXN][MAXN];
ll grid[MAXN][MAXN];
ll dp[MAXN][MAXN][MAXN][MAXN];
ll N, M;
ll f(ll x1, ll y1, ll x2, ll y2) {
if (x1 == x2 && y1 == y2) {
return 0;
}
if (dp[x1][y1][x2][y2] != -1) {
return dp[x1][y1][x2][y2];
}
ll curr = 1e13;
for (ll i = x1; i<x2; i++) {
curr = min(curr, f(x1, y1, i, y2)+f(i+1, y1, x2, y2));
}
for (ll i = y1; i<y2; i++) {
curr = min(curr, f(x1, y1, x2, i)+f(x1, i+1, x2, y2));
}
curr+=pref[x2][y2]-pref[x2][y1-1]-pref[x1-1][y2]+pref[x1-1][y1-1];
dp[x1][y1][x2][y2] = curr;
return curr;
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
for (ll i = 1; i<=N; i++) {
for (ll j = 1; j <= M; j++) {
cin >> grid[i][j];
}
}
memset(dp, -1, sizeof(dp));
for (ll i = 1; i<=N; i++) {
for (ll j = 1; j<=M; j++) {
pref[i][j]+=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+grid[i][j];
}
}
cout << f(1, 1, N, M) << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
53376 KB |
Output is correct |
2 |
Correct |
31 ms |
53240 KB |
Output is correct |
3 |
Correct |
32 ms |
53248 KB |
Output is correct |
4 |
Correct |
31 ms |
53376 KB |
Output is correct |
5 |
Correct |
33 ms |
53248 KB |
Output is correct |
6 |
Correct |
32 ms |
53240 KB |
Output is correct |
7 |
Correct |
32 ms |
53240 KB |
Output is correct |
8 |
Correct |
37 ms |
53368 KB |
Output is correct |
9 |
Correct |
40 ms |
53376 KB |
Output is correct |
10 |
Correct |
46 ms |
53240 KB |
Output is correct |
11 |
Correct |
50 ms |
53368 KB |
Output is correct |
12 |
Correct |
71 ms |
53368 KB |
Output is correct |
13 |
Correct |
99 ms |
53368 KB |
Output is correct |
14 |
Correct |
50 ms |
53376 KB |
Output is correct |
15 |
Correct |
122 ms |
53368 KB |
Output is correct |
16 |
Correct |
39 ms |
53368 KB |
Output is correct |
17 |
Correct |
63 ms |
53376 KB |
Output is correct |
18 |
Correct |
251 ms |
53496 KB |
Output is correct |
19 |
Correct |
408 ms |
53376 KB |
Output is correct |
20 |
Correct |
482 ms |
53368 KB |
Output is correct |