Submission #840474

#TimeUsernameProblemLanguageResultExecution timeMemory
840474overwatch9Raisins (IOI09_raisins)C++17
30 / 100
141 ms25952 KiB
#include <iostream> #include <vector> using namespace std; vector <vector <int>> grid; vector <vector <int>> pfx; const int maxn = 50 + 1; int dp[maxn][maxn][maxn][maxn]; int solve(int r1, int r2, int c1, int c2) { if (r1 == r2 && c1 == c2) return 0; if (dp[r1][r2][c1][c2] != -1) return dp[r1][r2][c1][c2]; int ans = 1e9; int x = pfx[r2][c2] - pfx[r2][c1-1] - pfx[r1-1][c2] + pfx[r2-1][c1-1]; for (int i = r1; i < r2; i++) { ans = min(ans, solve(r1, i, c1, c2) + solve(i+1, r2, c1, c2) + x); } for (int i = c1; i < c2; i++) { ans = min(ans, solve(r1, r2, c1, i) + solve(r1, r2, i+1, c2) + x); } dp[r1][r2][c1][c2] = ans; return ans; } int main() { int n, m; cin >> n >> m; grid = pfx = vector <vector <int>> (n+1, vector <int> (m+1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) cin >> grid[i][j]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int l = 1; l <= m; l++) { for (int k = 1; k <= m; k++) dp[i][j][l][k] = -1; } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { pfx[i][j] = grid[i][j]; pfx[i][j] += pfx[i-1][j] + pfx[i][j-1] - pfx[i-1][j-1]; } } cout << solve(1, n, 1, m) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...