# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
212277 |
2020-03-22T16:26:10 Z |
jk89 |
Raisins (IOI09_raisins) |
C++14 |
|
637 ms |
21244 KB |
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
#define f first
#define s second
const int MAXN = 51;
const int INF = 2e9 + 3;
int pref[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];
int rob(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 mn = INF;
for (int i = x1; i < x2; i++)
mn = min(mn, rob(x1, y1, i, y2) + rob(i + 1, y1, x2, y2));
for (int i = y1; i < y2; i++)
mn = min(mn, rob(x1, y1, x2, i) + rob(x1, i + 1, x2, y2));
dp[x1][y1][x2][y2] = mn + pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
return dp[x1][y1][x2][y2];
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &pref[i][j]);
pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
}
printf("%d", rob(1, 1, n, m));
return 0;
}
Compilation message
raisins.cpp: In function 'int main()':
raisins.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
raisins.cpp:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &pref[i][j]);
~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
512 KB |
Output is correct |
6 |
Correct |
5 ms |
896 KB |
Output is correct |
7 |
Correct |
5 ms |
1024 KB |
Output is correct |
8 |
Correct |
14 ms |
2688 KB |
Output is correct |
9 |
Correct |
19 ms |
3712 KB |
Output is correct |
10 |
Correct |
26 ms |
4352 KB |
Output is correct |
11 |
Correct |
22 ms |
3712 KB |
Output is correct |
12 |
Correct |
69 ms |
7416 KB |
Output is correct |
13 |
Correct |
107 ms |
9388 KB |
Output is correct |
14 |
Correct |
34 ms |
4600 KB |
Output is correct |
15 |
Correct |
132 ms |
10336 KB |
Output is correct |
16 |
Correct |
16 ms |
3712 KB |
Output is correct |
17 |
Correct |
57 ms |
7288 KB |
Output is correct |
18 |
Correct |
363 ms |
15992 KB |
Output is correct |
19 |
Correct |
550 ms |
19576 KB |
Output is correct |
20 |
Correct |
637 ms |
21244 KB |
Output is correct |