Submission #798155

#	Time	Username	Problem	Language	Result	Execution time	Memory
798155		YassirSalama	Raisins (IOI09_raisins)	C++14	100 / 100	413 ms	53276 KiB

raisins

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int tab[51][51];
int memo[51][51][51][51];
int solve(int xmin,int xmax,int ymin,int ymax)
{
  	if(xmin==xmax&&ymin==ymax) return 0;
    if(memo[xmin][xmax][ymin][ymax]!=-1)
    return memo[xmin][xmax][ymin][ymax];
    int ans=10000000000000000,cur=0;
    for(int x=xmin;x<=xmax;x++)
    {
        for(int y=ymin;y<=ymax;y++)
            cur+=tab[x][y];
    }
    if((xmax-xmin==1 && ymax-ymin==0)||(xmax-xmin==0 && ymax-ymin==1))
    return cur;
    for(int x=xmin+1;x<=xmax;x++)
        ans=min(ans,solve(xmin,x-1,ymin,ymax)+solve(x,xmax,ymin,ymax)+cur);
    for(int y=ymin+1;y<=ymax;y++)
        ans=min(ans,solve(xmin,xmax,ymin,y-1)+solve(xmin,xmax,y,ymax)+cur);
    memo[xmin][xmax][ymin][ymax]=ans;
    return ans;
}
signed main()
{
    memset(memo,-1,sizeof(memo));
    int n,m;
    cin>>n>>m;
    for(int x=0;x<n;x++)
    {
        for(int y=0;y<m;y++)
            cin>>tab[x][y];
    }
    cout<<solve(0,n-1,0,m-1);
}

• Subtask 1: 100 / 100