Submission #863375

#	Time	Username	Problem	Language	Result	Execution time	Memory
863375		HuyQuang_re_Zero	Raisins (IOI09_raisins)	C++14	100 / 100	179 ms	36440 KiB

raisins

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 55
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
int sum[N][N],f[N][N][N][N],n,m,i,j;
int get(int x1,int y1,int x2,int y2)
{
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int cal(int x1,int y1,int x2,int y2)
{
    if(x1==x2 && y1==y2) return 0;
    if(f[x1][y1][x2][y2]>-1) return f[x1][y1][x2][y2];
    int res=round(1e9),k=get(x1,y1,x2,y2);
    for(int i=x1;i<x2;i++) res=min(res,cal(x1,y1,i,y2)+cal(i+1,y1,x2,y2)+k);
    for(int i=y1;i<y2;i++) res=min(res,cal(x1,y1,x2,i)+cal(x1,i+1,x2,y2)+k);
    return f[x1][y1][x2][y2]=res;
}
int main()
{
 //   freopen("raisins.inp","r",stdin);
   // freopen("raisins.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            cin>>sum[i][j];
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    memset(f,-1,sizeof(f));
    cout<<cal(1,1,n,m);
}

• Subtask 1: 100 / 100