Submission #856137

#TimeUsernameProblemLanguageResultExecution timeMemory
856137IrateRaisins (IOI09_raisins)C++14
100 / 100
455 ms29096 KiB
#include<bits/stdc++.h> using namespace std; const int mxN = 52; int grid[mxN][mxN], pref[mxN][mxN], dp[mxN][mxN][mxN][mxN]; int rec(int x1, int y1, int x2, int y2){ int sum = pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1], res = 1e9; if(x1 == x2 && y1 == y2)return 0; if(dp[x1][y1][x2][y2] != -1)return dp[x1][y1][x2][y2]; for(int i = x1 + 1;i <= x2;++i){ res = min(res, sum + rec(i, y1, x2, y2) + rec(x1, y1, i - 1, y2)); } for(int i = y1 + 1;i <= y2;++i){ res = min(res, sum + rec(x1, y1, x2, i - 1) + rec(x1, i, x2, y2)); } return dp[x1][y1][x2][y2] = res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; for(int i = 0;i < mxN;++i){ for(int j = 0;j < mxN;++j){ for(int k = 0;k < mxN;++k){ for(int l = 0;l < mxN;++l){ dp[i][j][k][l] = -1; } } } } for(int i = 1;i <= n;++i){ for(int j = 1;j <= m;++j){ cin >> grid[i][j]; pref[i][j] = pref[i - 1][j] + pref[i][j - 1] + grid[i][j] - pref[i - 1][j - 1]; } } cout << rec(1, 1, n, m); }
#Verdict Execution timeMemoryGrader output
Fetching results...