Submission #337489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
337489	2020-12-21T02:13:44 Z	arbor	Raisins (IOI09_raisins)	C++17	100 / 100	925 ms	23020 KB

raisins

#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) {
    int &ret = dp[x1][y1][x2][y2];
    if (ret) return ret;
    if (x1 == x2 && y1 == y2) return 0;
    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));
    return ret += ps[x2][y2] - ps[x2][y1 - 1] - ps[x1 - 1][y2] + ps[x1 - 1][y1 - 1];
}

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;
}

Subtask #1

100.0 / 100.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	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	620 KB	Output is correct
6	Correct	1 ms	876 KB	Output is correct
7	Correct	2 ms	1004 KB	Output is correct
8	Correct	12 ms	2796 KB	Output is correct
9	Correct	27 ms	3948 KB	Output is correct
10	Correct	30 ms	4588 KB	Output is correct
11	Correct	25 ms	3948 KB	Output is correct
12	Correct	92 ms	7788 KB	Output is correct
13	Correct	155 ms	9836 KB	Output is correct
14	Correct	40 ms	4844 KB	Output is correct
15	Correct	190 ms	10988 KB	Output is correct
16	Correct	17 ms	3820 KB	Output is correct
17	Correct	76 ms	7788 KB	Output is correct
18	Correct	497 ms	17388 KB	Output is correct
19	Correct	786 ms	21324 KB	Output is correct
20	Correct	925 ms	23020 KB	Output is correct