| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 337478 |
2020-12-21T02:03:52 Z |
arbor |
Raisins (IOI09_raisins) |
C++17 |
|
1010 ms |
22880 KB |
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 55;
int N, M, ps[MN][MN], dp[MN][MN][MN][MN];
int go(int x1, int y1, int x2, int y2) {
if (dp[x1][y1][x2][y2]) return dp[x1][y1][x2][y2];
if (x1 == x2 && y1 == y2) return 0;
int ret = 1e9;
for (int nx = x1 + 1; nx <= x2; nx++)
ret = min(ret, go(x1, y1, nx - 1, y2) + go(nx, y1, x2, y2));
for (int ny = y1 + 1; ny <= y2; ny++)
ret = min(ret, go(x1, y1, x2, ny - 1) + go(x1, ny, x2, y2));
ret += ps[x2][y2] - ps[x2][y1 - 1] - ps[x1 - 1][y1] + ps[x1 - 1][y1 - 1];
return dp[x1][y1][x2][y2] = ret;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> ps[i][j], ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
cout << go(1, 1, N, M) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 6 |
Correct |
1 ms |
876 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
1004 KB |
Output isn't correct |
| 8 |
Incorrect |
13 ms |
2796 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
3820 KB |
Output isn't correct |
| 10 |
Incorrect |
32 ms |
4716 KB |
Output isn't correct |
| 11 |
Incorrect |
28 ms |
3948 KB |
Output isn't correct |
| 12 |
Incorrect |
98 ms |
7788 KB |
Output isn't correct |
| 13 |
Incorrect |
168 ms |
9836 KB |
Output isn't correct |
| 14 |
Incorrect |
43 ms |
4844 KB |
Output isn't correct |
| 15 |
Correct |
206 ms |
10988 KB |
Output is correct |
| 16 |
Incorrect |
20 ms |
3820 KB |
Output isn't correct |
| 17 |
Incorrect |
85 ms |
7788 KB |
Output isn't correct |
| 18 |
Incorrect |
543 ms |
17388 KB |
Output isn't correct |
| 19 |
Correct |
866 ms |
21228 KB |
Output is correct |
| 20 |
Incorrect |
1010 ms |
22880 KB |
Output isn't correct |
