Submission #394403

#TimeUsernameProblemLanguageResultExecution timeMemory
394403iulia13Raisins (IOI09_raisins)C++14
75 / 100
1347 ms103912 KiB
#include <iostream> using namespace std; #define ll long long const int C = 51; ll dp[C][C][C][C]; ll a[C][C]; int main() { int n, m, i, j, ii, jj; cin >> n >> m; for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) { cin >> a[i][j]; a[i][j] += (a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1]); for (ii = 1; ii <= n; ii++) for (jj = 1; jj <= m; jj++) dp[i][j][ii][jj] = 1e9; } for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) dp[i][j][i][j] = 0; for (int l = 1; l <= n + m - 2; l++) for (int x1 = 1; x1 <= n; x1++) for (int y1 = 1; y1 <= n; y1++) for (int x2 = x1; x2 <= n && x2 - x1 <= l; x2++) { int y2 = y1 + (l - (x2 - x1)); ll x = a[x2][y2] + a[x1 - 1][y1 - 1] - a[x1 - 1][y2] - a[x2][y1 - 1]; for (i = x1; i < x2; i++) dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], dp[x1][y1][i][y2] + dp[i + 1][y1][x2][y2] + x); for (i = y1; i < y2; i++) dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], dp[x1][y1][x2][i] + dp[x1][i + 1][x2][y2] + x); } cout << dp[1][1][n][m]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...