Submission #1004735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004735		12345678	Raisins (IOI09_raisins)	C++17	100 / 100	112 ms	68432 KiB

raisins

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=55;

ll n, m, qs[nx][nx], dp[nx][nx][nx][nx];

ll area(int a, int b, int c, int d)
{
    return qs[c][d]-qs[c][b-1]-qs[a-1][d]+qs[a-1][b-1];
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>qs[i][j], qs[i][j]+=qs[i-1][j]+qs[i][j-1]-qs[i-1][j-1];
    for (int x=0; x<=n; x++)
    {
        for (int y=0; y<=m; y++)
        {
            for (int i=1; i+x<=n; i++)
            {
                for (int j=1; j+y<=m; j++)
                {
                    if (x==0&&y==0) dp[i][j][i][j]=0;
                    else
                    {
                        dp[i][j][i+x][j+y]=LLONG_MAX;
                        for (int md=i; md<i+x; md++) dp[i][j][i+x][j+y]=min(dp[i][j][i+x][j+y], dp[i][j][md][j+y]+dp[md+1][j][i+x][j+y]+area(i, j, i+x, j+y));
                        for (int md=j; md<j+y; md++) dp[i][j][i+x][j+y]=min(dp[i][j][i+x][j+y], dp[i][j][i+x][md]+dp[i][md+1][i+x][j+y]+area(i, j, i+x, j+y));
                    }
                    //cout<<"debug "<<i<<' '<<j<<' '<<i+x<<' '<<j+y<<' '<<dp[i][j][i+x][j+y]<<'\n';
                    //cout<<"area "<<area(i, j, i+x, j+y)<<'\n';
                }
            }
        }
    }
    cout<<dp[1][1][n][m];
}

• Subtask 1: 100 / 100