Submission #989774

#	Time	Username	Problem	Language	Result	Execution time	Memory
989774		aaaaaarroz	Raisins (IOI09_raisins)	C++17	100 / 100	588 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