# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
394403 | iulia13 | Raisins (IOI09_raisins) | C++14 | 1347 ms | 103912 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 <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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |