Submission #839045

#TimeUsernameProblemLanguageResultExecution timeMemory
839045VMaksimoski008Raisins (IOI09_raisins)C++14
15 / 100
5086 ms57580 KiB
#include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define uniq(x) x.erase(unique(all(x)), x.end()) #define rall(x) x.rbegin(), x.rend() #define int long long using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; const double eps = 1e-9; void setIO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n, m; int mat[52][52]; ll prefix[52][52]; ll dp[52][52][52][52]; ll query(int x1, int y1, int x2, int y2) { ll ans = 0; ans += prefix[x2][y2]; ans -= prefix[x1-1][y2]; ans -= prefix[x2][y1-1]; ans += prefix[x1-1][y1-1]; return ans; } ll f(int x1, int y1, int x2, int y2) { if(x1 == x2 && y1 == y2) return 0; if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2]; //cout << "(" << x1 << " " << y1 << "), (" << x2 << " " << y2 << ")\n"; ll ans = 1e18; //make horizontal cut for(int i=x1; i<x2; i++) { ans = min(ans, f(x1, y1, i, y2) + f(i+1, y1, x2, y2)); } //make vertical cut for(int i=y1; i<y2; i++) { ans = min(ans, f(x1, y1, x2, i) + f(x1, i+1, x2, y2)); } return dp[x1][y1][x2][y1] = ans + query(x1, y1, x2, y2); } int32_t main() { setIO(); cin >> n >> m; memset(prefix, 0, sizeof(prefix)); memset(dp, -1, sizeof(dp)); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin >> mat[i][j]; //build prefix table for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { prefix[i][j] += mat[i][j]; prefix[i][j] += prefix[i-1][j]; prefix[i][j] += prefix[i][j-1]; prefix[i][j] -= prefix[i-1][j-1]; } } cout << f(1, 1, n, m) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...