Submission #1204211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204211		Newtonabc	Raisins (IOI09_raisins)	C++20	100 / 100	579 ms	26088 KiB

raisins

#include<bits/stdc++.h>
using namespace std;
int a[60][60],qs[60][60],dp[51][51][51][51];
int f(int a,int b,int c,int d){
    if(dp[a][b][c][d]!=-1) return dp[a][b][c][d];
    if(a==c && b==d) return dp[a][b][c][d]=0;
    int mn=INT_MAX,now=qs[c][d]-qs[a-1][d]-qs[c][b-1]+qs[a-1][b-1];
    for(int x=b;x<d;x++){
        mn=min(mn,f(a,b,c,x)+f(a,x+1,c,d)+now);
    }
    for(int x=a;x<c;x++){
        mn=min(mn,f(a,b,x,d)+f(x+1,b,c,d)+now);
    }
    return dp[a][b][c][d]=mn;
}
int main(){
    int n,m;
    cin>>n >>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            qs[i][j]=qs[i-1][j]+qs[i][j-1]-qs[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int x=1;x<=n;x++){
                for(int y=1;y<=m;y++){
                    dp[i][j][x][y]=-1;
                }
            }
        }
    }
    int ret=f(1,1,n,m);
    cout<<ret;
}

• Subtask 1: 100 / 100