Submission #953861

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
953861	2024-03-26T18:25:48 Z	Ariadna	Raisins (IOI09_raisins)	C++14	100 / 100	705 ms	29528 KB

raisins

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vi3 = vector<vii>;
using vi4 = vector<vi3>;

vii r, sum;
vi4 dp;

int value(int x1, int y1, int x2, int y2) {
    return sum[x2+1][y2+1] - sum[x1][y2+1] - sum[x2+1][y1] + sum[x1][y1];
}

int raisins(int x1, int y1, int x2, int y2) {
    if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];

    if (x1 == x2 && y1 == y2) return dp[x1][y1][x2][y2] = 0;

    dp[x1][y1][x2][y2] = 1e9;
    for (int x = x1; x < x2; ++x) {
        dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], raisins(x1, y1, x, y2) + raisins(x+1, y1, x2, y2) + value(x1, y1, x2, y2));
    }
    for (int y = y1; y < y2; ++y) {
        dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], raisins(x1, y1, x2, y) + raisins(x1, y+1, x2, y2) + value(x1, y1, x2, y2));
    }

    return dp[x1][y1][x2][y2];
}

int main() {
    int n, m;
    cin >> n >> m;
    r = vii (n, vi(m));
    sum = vii(n+1, vi(m+1, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> r[i][j];
            sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + r[i][j];
        }
    }
    dp = vi4(n, vi3(m, vii(n, vi(m, -1))));
    cout << raisins(0, 0, n-1, m-1) << '\n';

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	344 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	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	8 ms	1372 KB	Output is correct
9	Correct	14 ms	2016 KB	Output is correct
10	Correct	22 ms	2628 KB	Output is correct
11	Correct	18 ms	2140 KB	Output is correct
12	Correct	70 ms	5724 KB	Output is correct
13	Correct	116 ms	8280 KB	Output is correct
14	Correct	30 ms	2908 KB	Output is correct
15	Correct	141 ms	9596 KB	Output is correct
16	Correct	12 ms	1880 KB	Output is correct
17	Correct	60 ms	4700 KB	Output is correct
18	Correct	374 ms	18520 KB	Output is correct
19	Correct	612 ms	26964 KB	Output is correct
20	Correct	705 ms	29528 KB	Output is correct