Submission #730150

#	Time	Username	Problem	Language	Result	Execution time	Memory
730150		lucri	Raisins (IOI09_raisins)	C++17	100 / 100	286 ms	30020 KiB

raisins

#include <iostream>
using namespace std;
int n,m,a[55][55],pd[55][55][55][55];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            cin>>a[i][j];
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            for(int ii=1;ii<=n;++ii)
                for(int jj=1;jj<=m;++jj)
                    pd[i][j][ii][jj]=1000000000;
    for(int l=1;l<=n;++l)
        for(int c=1;c<=m;++c)
            for(int i=1;i+l-1<=n;++i)
                for(int j=1;j+c-1<=m;++j)
                {
                    int ii=i+l-1;
                    int jj=j+c-1;
                    if(i==ii&&j==jj)
                        pd[i][j][ii][jj]=0;
                    else
                    {
                        for(int iii=i+1;iii<=ii;++iii)
                            pd[i][j][ii][jj]=min(pd[i][j][ii][jj],pd[i][j][iii-1][jj]+pd[iii][j][ii][jj]);
                        for(int jjj=j+1;jjj<=jj;++jjj)
                            pd[i][j][ii][jj]=min(pd[i][j][ii][jj],pd[i][j][ii][jjj-1]+pd[i][jjj][ii][jj]);
                        pd[i][j][ii][jj]+=a[ii][jj]-a[i-1][jj]-a[ii][j-1]+a[i-1][j-1];
                    }
                }
    cout<<pd[1][1][n][m];
    return 0;
}

• Subtask 1: 100 / 100