Submission #1209352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209352		InternetPerson10	Raisins (IOI09_raisins)	C++20	100 / 100	404 ms	22080 KiB

raisins

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int a[51][51];
int dp[51][51][51][51];
int su[51][51];

int pref(int r1, int c1, int r2, int c2) {
    return su[r2][c2] - su[r2][c1] - su[r1][c2] + su[r1][c1];
}

int calc(int r1, int c1, int r2, int c2) {
    if(dp[r1][c1][r2][c2] != -1) return dp[r1][c1][r2][c2];
    if(r1 == r2 - 1 && c1 == c2 - 1) return dp[r1][c1][r2][c2] = 0;
    int ans = 999999999;
    for(int r = r1 + 1; r < r2; r++) {
        ans = min(ans, calc(r1, c1, r, c2) + calc(r, c1, r2, c2));
    }
    for(int c = c1 + 1; c < c2; c++) {
        ans = min(ans, calc(r1, c1, r2, c) + calc(r1, c, r2, c2));
    }
    return dp[r1][c1][r2][c2] = ans + pref(r1, c1, r2, c2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int r, c;
    cin >> r >> c;
    for(int i = 0; i <= r; i++) {
        for(int j = 0; j <= c; j++) {
            su[i][j] = 0;
        }
    }
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> a[i][j];
            su[i+1][j+1] = su[i+1][j] + su[i][j+1] - su[i][j] + a[i][j];
        }
    }
    for(int i = 0; i <= r; i++) {
        for(int j = i; j <= r; j++) {
            for(int k = 0; k <= c; k++) {
                for(int l = k; l <= c; l++) {
                    dp[i][k][j][l] = -1;
                }
            }
        }
    }
    cout << calc(0, 0, r, c) << '\n';
}

• Subtask 1: 100 / 100