Submission #236225

#	Time	Username	Problem	Language	Result	Execution time	Memory
236225		nicolaalexandra	Raisins (IOI09_raisins)	C++14	25 / 100	5078 ms	384 KiB

raisins

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

int sp[DIM][DIM],a[DIM][DIM];
int n,m,i,j;
int solve (int x, int y, int x2, int y2){
    if (x == x2 && y == y2)
        return 0;

    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));

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

}
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: 25 / 100