| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 308762 |
2020-10-01T21:23:28 Z |
Temmie |
Raisins (IOI09_raisins) |
C++17 |
|
1503 ms |
44280 KB |
#include <bits/stdc++.h>
int n, m;
std::vector <std::vector <int>> g;
std::vector <std::vector <std::vector <std::vector <int>>>> dp(55, std::vector <std::vector <std::vector <int>>> (55, std::vector <std::vector <int>> (55, std::vector <int> (55, 0))));
int f(int x, int xx, int y, int yy) {
if (x == xx - 1 && y == yy - 1) return 0;
if (dp[x][xx][y][yy]) return dp[x][xx][y][yy];
int r = 1 << 30;
for (int i = x + 1; i < xx; i++)
r = std::min(r, f(x, i, y, yy) + f(i, xx, y, yy));
for (int i = y + 1; i < yy; i++)
r = std::min(r, f(x, xx, i, yy) + f(x, xx, y, i));
dp[x][xx][y][yy] = r + g[xx][yy] + g[x][y] - g[x][yy] - g[xx][y];
return dp[x][xx][y][yy];
}
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
std::cin >> n >> m;
g.resize(n + 1, std::vector <int> (m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
std::cin >> g[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
int ans = f(0, n, 0, m);
std::cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
44152 KB |
Output is correct |
| 2 |
Correct |
37 ms |
44160 KB |
Output is correct |
| 3 |
Correct |
36 ms |
44152 KB |
Output is correct |
| 4 |
Correct |
38 ms |
44152 KB |
Output is correct |
| 5 |
Correct |
38 ms |
44160 KB |
Output is correct |
| 6 |
Correct |
36 ms |
44152 KB |
Output is correct |
| 7 |
Correct |
37 ms |
44152 KB |
Output is correct |
| 8 |
Correct |
50 ms |
44160 KB |
Output is correct |
| 9 |
Correct |
61 ms |
44160 KB |
Output is correct |
| 10 |
Correct |
74 ms |
44160 KB |
Output is correct |
| 11 |
Correct |
66 ms |
44160 KB |
Output is correct |
| 12 |
Correct |
168 ms |
44152 KB |
Output is correct |
| 13 |
Correct |
264 ms |
44280 KB |
Output is correct |
| 14 |
Correct |
88 ms |
44152 KB |
Output is correct |
| 15 |
Correct |
316 ms |
44160 KB |
Output is correct |
| 16 |
Correct |
60 ms |
44152 KB |
Output is correct |
| 17 |
Correct |
155 ms |
44160 KB |
Output is correct |
| 18 |
Correct |
804 ms |
44280 KB |
Output is correct |
| 19 |
Correct |
1277 ms |
44280 KB |
Output is correct |
| 20 |
Correct |
1503 ms |
44240 KB |
Output is correct |
