Submission #964341

#TimeUsernameProblemLanguageResultExecution timeMemory
964341anangoRaisins (IOI09_raisins)C++17
100 / 100
645 ms55432 KiB
#include <bits/stdc++.h> #define int long long using namespace std; vector<vector<int>> grid; vector<vector<int>> pref; vector<vector<vector<vector<int>>>> dp; //(i,j) and (k,l) int rect(int a, int b, int c, int d) { return pref[c+1][d+1]-pref[c+1][b]-pref[a][d+1]+pref[a][b]; } signed main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int n,m; cin >> n >> m; int INF=1000000007; dp=vector(n,vector(m,vector(n,vector<int>(m,INF)))); pref=vector(n+1,vector<int>(m+1,0)); grid=vector(n,vector<int>(m,0)); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { int x; cin >> x; grid[i][j] = x; } } for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { pref[i][j] = pref[i][j-1]+pref[i-1][j]-pref[i-1][j-1]+grid[i-1][j-1]; } } for (int wid=0; wid<m; wid++) { for (int hei=0; hei<n; hei++) { for (int tl=0; tl+hei<n; tl++) { for (int tr=0; tr+wid<m; tr++) { int bl=tl+hei; int br=tr+wid; if (wid==0 && hei==0) { dp[tl][tr][bl][br] = 0; } else { int R=rect(tl,tr,bl,br); int ans=INF; for (int hcut=tl; hcut<bl; hcut++) { ans=min(ans,dp[tl][tr][hcut][br]+dp[hcut+1][tr][bl][br]+R); } for (int vcut=tr; vcut<br; vcut++) { ans=min(ans,dp[tl][tr][bl][vcut]+dp[tl][vcut+1][bl][br]+R); } dp[tl][tr][bl][br] = ans; } //cout << tl <<" " << tr << " " << bl <<" " << br << " " << dp[tl][tr][bl][br] << endl; } } } } cout << dp[0][0][n-1][m-1] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...