Submission #1083108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083108		toast12	Raisins (IOI09_raisins)	C++14	100 / 100	478 ms	33372 KiB

raisins

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

vector<vector<vector<vector<int>>>> dp;
vector<vector<int>> ps;

// minimum cost to cut a piece of chocolate completely with corners at (i, j) and (k, l)
int cut(int i, int j, int k, int l) {
    if (i == k && j == l)
        return 0;
    if (dp[i][j][k][l] != -1)
        return dp[i][j][k][l];
    int x = ps[k][l]-ps[k][j-1]-ps[i-1][l]+ps[i-1][j-1];
    int ans = INT_MAX;
    // only one row left
    if (i == k) {
        // only two columns left
        if (j+1 == l)
            return x;
        for (int col = j; col < l; col++) {
            ans = min(ans, x+cut(i, j, k, col)+cut(i, col+1, k, l));
        }
    }
    // only one column left
    else if (j == l) {
        // only two rows left
        if (i+1 == k)
            return x;
        for (int row = i; row < k; row++) {
            ans = min(ans, x+cut(i, j, row, l)+cut(row+1, j, k, l));
        }
    }
    else {
        // iterate over all horizontal cuts
        for (int h = i; h < k; h++) {
            ans = min(ans, x+cut(i, j, h, l)+cut(h+1, j, k, l));
        }
        // iterate over all vertical cuts
        for (int v = j; v < l; v++) {
            ans = min(ans, x+cut(i, j, k, v)+cut(i, v+1, k, l));
        }
    }
    if (ans == INT_MAX)
        ans = x;
    return dp[i][j][k][l] = ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n+1, vector<int>(m+1));
    ps.resize(n+1, vector<int>(m+1));
    dp.resize(n+1, vector<vector<vector<int>>>(m+1, vector<vector<int>>(n+1, vector<int>(m+1, -1))));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ps[i][j] += ps[i][j-1]+grid[i][j];
        }
        for (int j = 1; j <= m; j++) {
            ps[i][j] += ps[i-1][j];
        }
    }
    cout << cut(1, 1, n, m) << '\n';
    return 0;
}

• Subtask 1: 100 / 100