#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
const ll N = 50+5 , INF = 1e18 , MOD = 1e9+7;
vector<vector<ll>> grid(N,vector<ll>(N)) , presum(N,vector<ll>(N));
ll dp[N][N][N][N];
ll go(ll ri , ll re , ll ci , ll ce){
if(ri == re && ci == ce) return 0;
if(dp[ri][re][ci][ce] != -1) return dp[ri][re][ci][ce];
ll ans = INF;
ll cost = presum[re][ce]-presum[ri-1][ce]-presum[re][ci-1]+presum[ri-1][ci-1];
for(ll i = ri; i < re; i++) ans = min(ans,cost+go(ri,i,ci,ce)+go(i+1,re,ci,ce));
for(ll j = ci; j < ce; j++) ans = min(ans,cost+go(ri,re,ci,j)+go(ri,re,j+1,ce));
return dp[ri][re][ci][ce] = ans;
}
void solve(){
ll n,m;
cin >> n >> m;
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= m; j++){
cin >> grid[i][j];
presum[i][j] = presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+grid[i][j];
}
}
memset(dp,-1,sizeof dp);
cout << go(1,n,1,m);
}
int main(){
fast;
ll tc = 1;
// cin >> tc;
while(tc--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
71884 KB |
Output is correct |
2 |
Correct |
27 ms |
71916 KB |
Output is correct |
3 |
Correct |
26 ms |
71892 KB |
Output is correct |
4 |
Correct |
27 ms |
72008 KB |
Output is correct |
5 |
Correct |
26 ms |
71884 KB |
Output is correct |
6 |
Correct |
29 ms |
71896 KB |
Output is correct |
7 |
Correct |
33 ms |
71972 KB |
Output is correct |
8 |
Correct |
30 ms |
71984 KB |
Output is correct |
9 |
Correct |
31 ms |
71860 KB |
Output is correct |
10 |
Correct |
33 ms |
71884 KB |
Output is correct |
11 |
Correct |
32 ms |
71884 KB |
Output is correct |
12 |
Correct |
44 ms |
71920 KB |
Output is correct |
13 |
Correct |
56 ms |
71996 KB |
Output is correct |
14 |
Correct |
34 ms |
71952 KB |
Output is correct |
15 |
Correct |
63 ms |
71996 KB |
Output is correct |
16 |
Correct |
30 ms |
72000 KB |
Output is correct |
17 |
Correct |
40 ms |
71944 KB |
Output is correct |
18 |
Correct |
148 ms |
72012 KB |
Output is correct |
19 |
Correct |
195 ms |
72064 KB |
Output is correct |
20 |
Correct |
221 ms |
72004 KB |
Output is correct |