Submission #236235

#	Time	Username	Problem	Language	Result	Execution time	Memory
236235		nicolaalexandra	Raisins (IOI09_raisins)	C++14	100 / 100	817 ms	21624 KiB

raisins

#include <bits/stdc++.h>
#define DIM 52
#define INF 2000000000
using namespace std;

int sp[DIM][DIM],a[DIM][DIM],opt[DIM][DIM][DIM][DIM];
int n,m,i,j;

int solve (int x, int y, int x2, int y2){
    if (x == x2 && y == y2)
        return 0;

    if (opt[x][y][x2][y2]) /// am mai calculat deja starea asta
        return opt[x][y][x2][y2];

    int sol = INF;

    for (int i=y;i<y2;i++)
        sol = min (sol,solve(x,y,x2,i) + solve(x,i+1,x2,y2));

    for (int i=x;i<x2;i++)
        sol = min (sol,solve(x,y,i,y2) + solve(i+1,y,x2,y2));

    opt[x][y][x2][y2] = sol + sp[x2][y2] - sp[x2][y-1] - sp[x-1][y2] + sp[x-1][y-1];

    return opt[x][y][x2][y2];
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            cin>>a[i][j];
            sp[i][j] = sp[i-1][j] + sp[i][j-1] - sp[i-1][j-1] + a[i][j];
        }

    cout<<solve (1,1,n,m);


    return 0;
}

• Subtask 1: 100 / 100