Submission #882441

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
882441	2023-12-03T07:45:15 Z	Desh03	Raisins (IOI09_raisins)	C++17	100 / 100	161 ms	13456 KB

raisins

#include <bits/stdc++.h>

using namespace std;

const int MX = 51;
int dp[MX][MX][MX][MX];
int p[MX][MX];

int calc_dp(int l1, int r1, int l2, int r2) {
    if (l1 == r1 && l2 == r2) return 0;
    if (dp[l1][r1][l2][r2]) return dp[l1][r1][l2][r2];
    int mn = 1e9;
    for (int i = l1; i < r1; i++) {
        mn = min(mn, calc_dp(l1, i, l2, r2) + calc_dp(i + 1, r1, l2, r2));
    }
    for (int i = l2; i < r2; i++) {
        mn = min(mn, calc_dp(l1, r1, l2, i) + calc_dp(l1, r1, i + 1, r2));
    }
    return dp[l1][r1][l2][r2] = mn + p[r1][r2] - p[r1][l2 - 1] - p[l1 - 1][r2] + p[l1 - 1][l2 - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> p[i][j];
            p[i][j] += p[i][j - 1] + p[i - 1][j] - p[i - 1][j - 1];
        }
    }
    cout << calc_dp(1, n, 1, m) << '\n';
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	460 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	3 ms	1932 KB	Output is correct
9	Correct	7 ms	2908 KB	Output is correct
10	Correct	9 ms	3416 KB	Output is correct
11	Correct	7 ms	2396 KB	Output is correct
12	Correct	19 ms	5584 KB	Output is correct
13	Correct	29 ms	6732 KB	Output is correct
14	Correct	9 ms	2640 KB	Output is correct
15	Correct	36 ms	7484 KB	Output is correct
16	Correct	5 ms	4956 KB	Output is correct
17	Correct	17 ms	7604 KB	Output is correct
18	Correct	87 ms	11860 KB	Output is correct
19	Correct	136 ms	12444 KB	Output is correct
20	Correct	161 ms	13456 KB	Output is correct