Submission #767251

#TimeUsernameProblemLanguageResultExecution timeMemory
767251Gabi88Raisins (IOI09_raisins)C++14
100 / 100
944 ms88932 KiB
#include<bits/stdc++.h> using namespace std; #define LL long long LL n, m, dp[58][58][58][58], sub[58][58]; LL dodaj(int px, int py, int cx, int cy){ int d1 = 0, d2 = 0, d3 = 0; if (px >= 0 and py >= 0) d1 = sub[px][py]; if (px >= 0) d2 = sub[px][cy]; if (py >= 0) d3 = sub[cx][py]; return d1 + sub[cx][cy] - d2 - d3; } LL reks(int px, int py, int cx, int cy){ LL suma = dodaj(px-1, py-1, cx-1, cy-1), res = 1000000009; if (px+1 == cx and py+1 == cy) return dp[px][py][cx][cy]; else if (dp[px][py][cx][cy] >= suma) return dp[px][py][cx][cy]; // cout << suma << " -> " << px << " " << py << " " << cx << " " << cy << endl; for(int i=px+1; i < cx; i++) res = min(res, reks(px, py, i, cy) + reks(i, py, cx, cy) + suma); for(int i=py+1; i < cy; i++) res = min(res, reks(px, py, cx, i) + reks(px, i, cx, cy) + suma); // cout << px << " " << py << " | " << cx << " " << cy << " | " << res << endl; return dp[px][py][cx][cy] = res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i1=0; i1 < 58; i1++) for(int i2=0; i2 < 58; i2++) for(int i3=0; i3 < 58; i3++) for(int i4=0; i4 < 58; i4++) dp[i1][i2][i3][i4] = -1; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ cin >> dp[i][j][i+1][j+1]; if (i == 0 and j == 0) sub[0][0] = dp[0][0][1][1]; else if (i == 0) sub[0][j] = sub[0][j-1] + dp[0][j][1][j+1]; else if (j == 0) sub[i][0] = sub[i-1][0] + dp[i][0][i+1][1]; else sub[i][j] = sub[i][j-1] + sub[i-1][j] - sub[i-1][j-1] + dp[i][j][i+1][j+1]; } } cout << reks(0, 0, n, m)-sub[n-1][m-1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...