Submission #953861

#	Time	Username	Problem	Language	Result	Execution time	Memory
953861		Ariadna	Raisins (IOI09_raisins)	C++14	100 / 100	705 ms	29528 KiB

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 / 100