Submission #1020301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020301		AliHasanli	Raisins (IOI09_raisins)	C++17	100 / 100	517 ms	33816 KiB

raisins

#include<bits/stdc++.h>
using namespace std;
long long arr[50][50],dp[50][50][50][50],pre[50][50];
void com()
{
    pre[0][0]=arr[0][0];
    for(int j=1;j<50;j++)
        pre[0][j]=pre[0][j-1]+arr[0][j];
    for(int i=1;i<50;i++)
        for(int j=0;j<50;j++)
        {
            if(j==0)
                pre[i][j]=pre[i-1][j]+arr[i][j];
            else
                pre[i][j]=pre[i-1][j]-pre[i-1][j-1]+pre[i][j-1]+arr[i][j];
        }
}
long long sum(int x1,int y1,int x2,int y2)
{
    if(x1==0 && y1==0)
        return pre[x2][y2];
    else if(x1==0)
        return pre[x2][y2]-pre[x2][y1-1];
    else if(y1==0)
        return pre[x2][y2]-pre[x1-1][y2];
    return pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1];
}
long long f(int x1,int y1,int x2,int y2)
{
    long long ans=1000000000000000000;
    if(dp[x1][y1][x2][y2])return dp[x1][y1][x2][y2];
    if(x1==x2 && y1==y2)return dp[x1][y1][x2][y2]=0;
    for(int i=x1;i<x2;i++)
        ans=min(ans,sum(x1,y1,x2,y2)+f(x1,y1,i,y2)+f(i+1,y1,x2,y2));
    for(int j=y1;j<y2;j++)
        ans=min(ans,sum(x1,y1,x2,y2)+f(x1,y1,x2,j)+f(x1,j+1,x2,y2));
    return dp[x1][y1][x2][y2]=ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    cin>>arr[i][j];
    com();
    cout<<f(0,0,n-1,m-1);
    return 0;
}

• Subtask 1: 100 / 100