Submission #771873

#	Time	Username	Problem	Language	Result	Execution time	Memory
771873		cnastea	Raisins (IOI09_raisins)	C++14	100 / 100	748 ms	26516 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
int a[50][50];
int d[50][50][50][50];
bool b[50][50][50][50];

int f(int p, int q, int r, int s){
    if(p == r && q == s) {
        return 0;
    }
    if (b[p][q][r][s]) {
        return d[p][q][r][s];
    }
    else b[p][q][r][s] = 1;
    int m = 1e9, t = 0;
    for(int i = p; i <= r; i++){
        for(int j = q; j <= s; j++){
            t += a[i][j];
        }
    }
    for(int i = p+1; i <= r; i++){
        int x, y;
        x = f(p, q, i-1, s);
        y = f(i, q, r, s);
        m = min(m, x + y + t);
    }
    for(int i = q+1; i <= s; i++){
        int x, y;
        x = f(p, q, r, i-1);
        y = f(p, i, r, s);
        m = min(m, x + y + t);
    }
    d[p][q][r][s] = m;
    return m;
}

int main()
{
    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 << f(0, 0, n-1, m-1);
    return 0;
}

• Subtask 1: 100 / 100