Submission #1220443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220443		AlgorithmWarrior	Raisins (IOI09_raisins)	C++20	100 / 100	247 ms	21952 KiB

raisins

#include <bits/stdc++.h>
#define MAX 53

using namespace std;

int sp[MAX][MAX];
int dp[MAX][MAX][MAX][MAX];
int N,M;

void read()
{
    cin>>N>>M;
    int i,j;
    for(i=1;i<=N;++i)
        for(j=1;j<=M;++j)
            cin>>sp[i][j];
}

void precalc()
{
    int i,j;
    for(i=1;i<=N;++i)
        for(j=1;j<=M;++j)
            sp[i][j]+=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1];
}

int dpr(int l1,int c1,int l2,int c2)
{
    if(l1==l2 && c1==c2)
        return 0;
    if(dp[l1][c1][l2][c2])
        return dp[l1][c1][l2][c2];
    int i;
    dp[l1][c1][l2][c2]=1e9;
    for(i=l1;i<l2;++i)
        dp[l1][c1][l2][c2]=min(dp[l1][c1][l2][c2],dpr(l1,c1,i,c2)+dpr(i+1,c1,l2,c2));
    for(i=c1;i<c2;++i)
        dp[l1][c1][l2][c2]=min(dp[l1][c1][l2][c2],dpr(l1,c1,l2,i)+dpr(l1,i+1,l2,c2));
    dp[l1][c1][l2][c2]+=sp[l2][c2]-sp[l2][c1-1]-sp[l1-1][c2]+sp[l1-1][c1-1];
    return dp[l1][c1][l2][c2];
}

void write()
{
    cout<<dpr(1,1,N,M);
}

int main()
{
    read();
    precalc();
    write();
    return 0;
}

• Subtask 1: 100 / 100