oj.uz

Submission #593212

# Submission time Handle Problem Language Result Execution time Memory
593212 2022-07-10T15:14:43 Z Bench0310 Raisins (IOI09_raisins) C++17
100 / 100
 155 ms 24816 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=50;
int a[N][N];
int sum[N][N];
int dp[N][N][N][N];

void chmin(int &x,int y){x=min(x,y);}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin >> a[i][j];
            sum[i][j]=(i>0?sum[i-1][j]:0)+(j>0?sum[i][j-1]:0)-((i>0&&j>0)?sum[i-1][j-1]:0)+a[i][j];
        }
    }
    memset(dp,127,sizeof(dp));
    for(int sr=1;sr<=n;sr++)
    {
        for(int sc=1;sc<=m;sc++)
        {
            for(int li=0;li+sr-1<n;li++)
            {
                int ri=li+sr-1;
                for(int lj=0;lj+sc-1<m;lj++)
                {
                    int rj=lj+sc-1;
                    int s=(sum[ri][rj]-(li>0?sum[li-1][rj]:0)-(lj>0?sum[ri][lj-1]:0)+((li>0&&lj>0)?sum[li-1][lj-1]:0));
                    int &d=dp[li][ri][lj][rj];
                    if(sr==1&&sc==1) d=0;
                    //horizontal
                    for(int i=li;i<ri;i++) chmin(d,dp[li][i][lj][rj]+dp[i+1][ri][lj][rj]+s);
                    //vertical
                    for(int j=lj;j<rj;j++) chmin(d,dp[li][ri][lj][j]+dp[li][ri][j+1][rj]+s);
                }
            }
        }
    }
    cout << dp[0][n-1][0][m-1] << "\n";
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24784 KB Output is correct
2 Correct 11 ms 24696 KB Output is correct
3 Correct 9 ms 24788 KB Output is correct
4 Correct 9 ms 24752 KB Output is correct
5 Correct 10 ms 24788 KB Output is correct
6 Correct 10 ms 24712 KB Output is correct
7 Correct 10 ms 24772 KB Output is correct
8 Correct 12 ms 24752 KB Output is correct
9 Correct 12 ms 24716 KB Output is correct
10 Correct 12 ms 24788 KB Output is correct
11 Correct 12 ms 24784 KB Output is correct
12 Correct 20 ms 24800 KB Output is correct
13 Correct 31 ms 24796 KB Output is correct
14 Correct 14 ms 24788 KB Output is correct
15 Correct 32 ms 24800 KB Output is correct
16 Correct 12 ms 24784 KB Output is correct
17 Correct 21 ms 24780 KB Output is correct
18 Correct 77 ms 24792 KB Output is correct
19 Correct 140 ms 24812 KB Output is correct
20 Correct 155 ms 24816 KB Output is correct