Submission #235790

#TimeUsernameProblemLanguageResultExecution timeMemory
235790Haunted_CppRaisins (IOI09_raisins)C++17
25 / 100
114 ms36352 KiB
/** * author: Duarte Nobrega * created: 29.05.2020 **/ #include <bits/stdc++.h> using namespace std; const int N = 50 + 5; int g [N][N], s [N][N]; int dp [N][N][N][N]; int range_query (int x1, int y1, int x2, int y2) { return s[x2][y2] - (x1 - 1 >= 0 ? s[x1 - 1][y2] : 0) - (y1 - 1 >= 0 ? s[x2][y1 - 1] : 0) + (x1 - 1 >= 0 && y1 - 1 >= 0 ? s[x1 - 1][y1 - 1] : 0); } int r, c; int solve (int x1, int y1, int x2, int y2) { if (x1 > x2) return 0; if (y1 > y2) return 0; if (x1 == x2 && y1 == y2) return 0; int &res = dp[x1][y1][x2][y2]; if (~res) return res; res = 1e9; for (int i = x1; i <= (x1 + x2) / 2; i++) { int cima_x1 = x1; int cima_y1 = y1; int cima_x2 = i; int cima_y2 = y2; int baixo_x1 = i + 1; int baixo_y1 = y1; int baixo_x2 = x2; int baixo_y2 = y2; int cost_of_split = range_query (cima_x1, cima_y1, cima_x2, cima_y2) + range_query (baixo_x1, baixo_y1, baixo_x2, baixo_y2); int other = solve (cima_x1, cima_y1, cima_x2, cima_y2) + solve (baixo_x1, baixo_y1, baixo_x2, baixo_y2); res = min (res, cost_of_split + other); } for (int i = y1; i <= (y1 + y2) / 2; i++) { int cima_x1 = x1; int cima_y1 = y1; int cima_x2 = x2; int cima_y2 = i; int baixo_x1 = x1; int baixo_y1 = i + 1; int baixo_x2 = x2; int baixo_y2 = y2; int cost_of_split = range_query (cima_x1, cima_y1, cima_x2, cima_y2) + range_query (baixo_x1, baixo_y1, baixo_x2, baixo_y2); int other = solve (cima_x1, cima_y1, cima_x2, cima_y2) + solve (baixo_x1, baixo_y1, baixo_x2, baixo_y2); res = min (res, cost_of_split + other); } return res; } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> r >> c; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cin >> g[i][j]; } } s[0][0] = g[0][0]; for (int i = 1; i < c; i++) s[0][i] = s[0][i - 1] + g[0][i]; for (int i = 1; i < r; i++) s[i][0] = s[i - 1][0] + g[i][0]; for (int i = 1; i < r; i++) { for (int j = 1; j < c; j++) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + g[i][j]; } } memset (dp, -1, sizeof(dp)); cout << solve (0, 0, r - 1, c - 1) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...