Submission #1214899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214899		countless	Raisins (IOI09_raisins)	C++20	100 / 100	404 ms	24924 KiB

raisins

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

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int dp[50][50][50][50];
vector<vector<int>> grid, pref;

int query(int lr, int rr, int lc, int rc) {
    return { 0
        + pref[rr][rc]
        - (lr > 0 ? pref[lr-1][rc] : 0)
        - (lc > 0 ? pref[rr][lc-1] : 0)
        + (lr > 0 and lc > 0 ? pref[lr-1][lc-1] : 0)
    };
}

int decomp(int lr, int rr, int lc, int rc) {
    int sz = (rr - lr + 1) * (rc - lc + 1);
    if (sz == 1) return 0;
    if (dp[lr][rr][lc][rc] != -1) return dp[lr][rr][lc][rc];

    int mn = INT_MAX;

    for (int i = lr; i < rr; i++) {
        mn = min(mn, decomp(lr, i, lc, rc) + decomp(i+1, rr, lc, rc));
    }

    for (int i = lc; i < rc; i++) {
        mn = min(mn, decomp(lr, rr, lc, i) + decomp(lr, rr, i+1, rc));
    }

    return dp[lr][rr][lc][rc] = mn + query(lr, rr, lc, rc);
}

void solve() {
    int n, m; cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; i++) grid[i].resize(m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    pref = grid;
    for (int i = 1; i < n; i++) pref[i][0] += pref[i-1][0];
    for (int i = 1; i < m; i++) pref[0][i] += pref[0][i-1];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            pref[i][j] += pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
        }
    }

    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < 50; j++) {
            for (int k = 0; k < 50; k++) {
                for (int l = 0; l < 50; l++) {
                    dp[i][j][k][l] = -1;
                }
            }
        }
    }

    cout << decomp(0, n-1, 0, m-1) << endl;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 100 / 100