Submission #754892

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754892	2023-06-08T20:36:38 Z	Desh03	Raisins (IOI09_raisins)	C++17	100 / 100	197 ms	13520 KB

raisins

#include <bits/stdc++.h>
using namespace std;

const int MX = 51;
int dp[MX][MX][MX][MX];
int pre[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 + pre[r1][r2] - pre[r1][l2 - 1] - pre[l1 - 1][r2] + pre[l1 - 1][l2 - 1];
}

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	456 KB	Output is correct
6	Correct	1 ms	580 KB	Output is correct
7	Correct	1 ms	960 KB	Output is correct
8	Correct	4 ms	1748 KB	Output is correct
9	Correct	6 ms	2772 KB	Output is correct
10	Correct	8 ms	3156 KB	Output is correct
11	Correct	7 ms	2388 KB	Output is correct
12	Correct	27 ms	5728 KB	Output is correct
13	Correct	34 ms	6788 KB	Output is correct
14	Correct	10 ms	2644 KB	Output is correct
15	Correct	45 ms	7540 KB	Output is correct
16	Correct	8 ms	4948 KB	Output is correct
17	Correct	22 ms	7616 KB	Output is correct
18	Correct	108 ms	11820 KB	Output is correct
19	Correct	160 ms	12492 KB	Output is correct
20	Correct	197 ms	13520 KB	Output is correct