oj.uz

Submission #1004735

# Submission time Handle Problem Language Result Execution time Memory
1004735 2024-06-21T13:23:57 Z 12345678 Raisins (IOI09_raisins) C++17
100 / 100
 112 ms 68432 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 14684 KB Output is correct
7 Correct 2 ms 20828 KB Output is correct
8 Correct 3 ms 24920 KB Output is correct
9 Correct 5 ms 33112 KB Output is correct
10 Correct 5 ms 35160 KB Output is correct
11 Correct 5 ms 26972 KB Output is correct
12 Correct 16 ms 43612 KB Output is correct
13 Correct 21 ms 47452 KB Output is correct
14 Correct 7 ms 29212 KB Output is correct
15 Correct 25 ms 49500 KB Output is correct
16 Correct 6 ms 51544 KB Output is correct
17 Correct 14 ms 55644 KB Output is correct
18 Correct 54 ms 64084 KB Output is correct
19 Correct 93 ms 64092 KB Output is correct
20 Correct 112 ms 68432 KB Output is correct