Submission #1112792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112792		karok	Raisins (IOI09_raisins)	C++17	100 / 100	899 ms	72076 KiB

raisins

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

using ll = long long;
const int MAXN = 55;

ll dp[MAXN][MAXN][MAXN][MAXN];
int a[MAXN][MAXN];

ll rec(int ar, int ac, int br, int bc) {
    if(ar > br || ac > bc) return 0;
    if(ar == br && ac == bc) return 0;
    if(dp[ar][ac][br][bc] != -1) return dp[ar][ac][br][bc];

    ll res = LLONG_MAX;
    for(int i = ar;i < br;i++) { // row cut
        res = min(res, rec(ar, ac, i, bc) + rec(i + 1, ac, br, bc));
    }
    for(int i = ac; i < bc;i++) {
        res = min(res, rec(ar, ac, br, i) + rec(ar, i + 1, br, bc));

    }

    for(int i =ar;i <= br;i++) {
        for(int j = ac; j <= bc;j++) {
            res += a[i][j];
        }
    }
    return dp[ar][ac][br][bc] = res;
}

int main() {
    memset(dp, -1, sizeof(dp));
    int n, m;
    cin >> n >> m;
    for(int i =0;i < n;i++) {
        for(int j =0; j < m;j++) {
            cin >> a[i][j];
        }
    }
    cout << rec(0, 0, n - 1, m -1) << '\n';
}

• Subtask 1: 100 / 100