Submission #1214898

#TimeUsernameProblemLanguageResultExecution timeMemory
1214898countlessRaisins (IOI09_raisins)C++20
100 / 100
403 ms25000 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define sp <<" "<< #define endl "\n" int dp[50][50][50][50]; vector<vector<int>> grid, pref; int query(int lr, int rr, int lc, int rc) { return { 0 + pref[rr][rc] - (lr > 0 ? pref[lr-1][rc] : 0) - (lc > 0 ? pref[rr][lc-1] : 0) + (lr > 0 and lc > 0 ? pref[lr-1][lc-1] : 0) }; } int decomp(int lr, int rr, int lc, int rc) { int sz = (rr - lr + 1) * (rc - lc + 1); if (sz == 1) return 0; if (dp[lr][rr][lc][rc] != -1) return dp[lr][rr][lc][rc]; int mn = INT_MAX; for (int i = lr; i < rr; i++) { mn = min(mn, decomp(lr, i, lc, rc) + decomp(i+1, rr, lc, rc)); } for (int i = lc; i < rc; i++) { mn = min(mn, decomp(lr, rr, lc, i) + decomp(lr, rr, i+1, rc)); } return dp[lr][rr][lc][rc] = mn + query(lr, rr, lc, rc); } void solve() { int n, m; cin >> n >> m; grid.resize(n); for (int i = 0; i < n; i++) grid[i].resize(m); int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; sum += grid[i][j]; } } pref = grid; for (int i = 1; i < n; i++) pref[i][0] += pref[i-1][0]; for (int i = 1; i < m; i++) pref[0][i] += pref[0][i-1]; for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { pref[i][j] += pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]; } } for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { for (int k = 0; k < 50; k++) { for (int l = 0; l < 50; l++) { dp[i][j][k][l] = -1; } } } } cout << decomp(0, n-1, 0, m-1) << endl; } signed main() { cin.tie(0); ios_base::sync_with_stdio(false); int t = 1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...