Submission #412722

#	Time	Username	Problem	Language	Result	Execution time	Memory
412722		dolijan	Raisins (IOI09_raisins)	C++14	100 / 100	334 ms	36156 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
const int mn=55;
int a[mn][mn];
int dp[mn][mn][mn][mn];
int pref[mn][mn];
const int INF=1e9;
int prefiksnaoo(int i,int j,int x,int y)
{
   int prefiksna=0;
    if(i==0 && j==0) prefiksna=pref[x][y];
    else if(i==0) prefiksna=pref[x][y]-pref[x][j-1];
    else if(j==0) prefiksna=pref[x][y]-pref[i-1][y];
    else prefiksna=pref[x][y]+pref[i-1][j-1]-pref[x][j-1]-pref[i-1][y];
    return prefiksna;
}
int resi(int i,int j,int x,int y)
{
    if(dp[i][j][x][y]!=-1) return dp[i][j][x][y];
    int mn=INF;
    int prefiksna=prefiksnaoo(i,j,x,y);
    for(int k=j;k<y;k++)
    {
        //mn=min(mn,dp[i][j][x][k]+dp[i][k+1][x][y]+prefiksna);
        mn=min(mn,resi(i,j,x,k)+resi(i,k+1,x,y)+prefiksna);
    }
    for(int k=i;k<x;k++)
    {
        //mn=min(mn,dp[i][j][k][y]+dp[k+1][j][x][y]+prefiksna);
        mn=min(mn,resi(i,j,k,y)+resi(k+1,j,x,y)+prefiksna);
    }
    return dp[i][j][x][y]=mn;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<mn;i++)
        for(int j=0;j<mn;j++)
            for(int i1=0;i1<mn;i1++)
                for(int j1=0;j1<mn;j1++)   dp[i][j][i1][j1]=-1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
            dp[i][j][i][j]=0;
        }
    }
    pref[0][0]=a[0][0];
    for(int i=1;i<n;i++) pref[i][0]=pref[i-1][0]+a[i][0];
    for(int j=1;j<m;j++) pref[0][j]=pref[0][j-1]+a[0][j];
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
    }
    //cout<<pref[1][1]<<endl;
    //cout<<prefiksnaoo(0,1,1,1)<<endl;
    //cout<<prefiksnaoo(1,1,1,2)<<endl;
    cout<<resi(0,0,n-1,m-1);
}

• Subtask 1: 100 / 100