# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
964341 | anango | Raisins (IOI09_raisins) | C++17 | 645 ms | 55432 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |