Submission #757895

#TimeUsernameProblemLanguageResultExecution timeMemory
757895SanguineChameleonRaisins (IOI09_raisins)C++17
100 / 100
178 ms15588 KiB
#include <bits/stdc++.h> using namespace std; void just_do_it(); int main() { #ifdef KAMIRULEZ freopen("kamirulez.inp", "r", stdin); freopen("kamirulez.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); just_do_it(); return 0; } const int inf = 1e9 + 20; const int maxn = 55; int dp[maxn][maxn][maxn][maxn]; int pref[maxn][maxn]; void just_do_it() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> pref[i][j]; pref[i][j] += pref[i][j - 1]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { pref[i][j] += pref[i - 1][j]; } } for (int h = 1; h <= n; h++) { for (int w = 1; w <= m; w++) { if (h == 1 && w == 1) { continue; } for (int lx = 1, rx = h; rx <= n; lx++, rx++) { for (int ly = 1, ry = w; ry <= m; ly++, ry++) { int sum = pref[rx][ry] - pref[rx][ly - 1] - pref[lx - 1][ry] + pref[lx - 1][ly - 1]; dp[lx][rx][ly][ry] = inf; for (int k = lx; k < rx; k++) { dp[lx][rx][ly][ry] = min(dp[lx][rx][ly][ry], sum + dp[lx][k][ly][ry] + dp[k + 1][rx][ly][ry]); } for (int k = ly; k < ry; k++) { dp[lx][rx][ly][ry] = min(dp[lx][rx][ly][ry], sum + dp[lx][rx][ly][k] + dp[lx][rx][k + 1][ry]); } } } } } cout << dp[1][n][1][m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...