oj.uz

Submission #412722

# Submission time Handle Problem Language Result Execution time Memory
412722 2021-05-27T11:44:54 Z dolijan Raisins (IOI09_raisins) C++14
100 / 100
 334 ms 36156 KB 
#include <bits/stdc++.h>
using namespace std;
const int mn=55;
int a[mn][mn];
int dp[mn][mn][mn][mn];
int pref[mn][mn];
const int INF=1e9;
int prefiksnaoo(int i,int j,int x,int y)
{
   int prefiksna=0;
    if(i==0 && j==0) prefiksna=pref[x][y];
    else if(i==0) prefiksna=pref[x][y]-pref[x][j-1];
    else if(j==0) prefiksna=pref[x][y]-pref[i-1][y];
    else prefiksna=pref[x][y]+pref[i-1][j-1]-pref[x][j-1]-pref[i-1][y];
    return prefiksna;
}
int resi(int i,int j,int x,int y)
{
    if(dp[i][j][x][y]!=-1) return dp[i][j][x][y];
    int mn=INF;
    int prefiksna=prefiksnaoo(i,j,x,y);
    for(int k=j;k<y;k++)
    {
        //mn=min(mn,dp[i][j][x][k]+dp[i][k+1][x][y]+prefiksna);
        mn=min(mn,resi(i,j,x,k)+resi(i,k+1,x,y)+prefiksna);
    }
    for(int k=i;k<x;k++)
    {
        //mn=min(mn,dp[i][j][k][y]+dp[k+1][j][x][y]+prefiksna);
        mn=min(mn,resi(i,j,k,y)+resi(k+1,j,x,y)+prefiksna);
    }
    return dp[i][j][x][y]=mn;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<mn;i++)
        for(int j=0;j<mn;j++)
            for(int i1=0;i1<mn;i1++)
                for(int j1=0;j1<mn;j1++)   dp[i][j][i1][j1]=-1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
            dp[i][j][i][j]=0;
        }
    }
    pref[0][0]=a[0][0];
    for(int i=1;i<n;i++) pref[i][0]=pref[i-1][0]+a[i][0];
    for(int j=1;j<m;j++) pref[0][j]=pref[0][j-1]+a[0][j];
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
    }
    //cout<<pref[1][1]<<endl;
    //cout<<prefiksnaoo(0,1,1,1)<<endl;
    //cout<<prefiksnaoo(1,1,1,2)<<endl;
    cout<<resi(0,0,n-1,m-1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36044 KB Output is correct
2 Correct 18 ms 36044 KB Output is correct
3 Correct 17 ms 36044 KB Output is correct
4 Correct 17 ms 36084 KB Output is correct
5 Correct 17 ms 36052 KB Output is correct
6 Correct 17 ms 36020 KB Output is correct
7 Correct 17 ms 36116 KB Output is correct
8 Correct 21 ms 36008 KB Output is correct
9 Correct 22 ms 36044 KB Output is correct
10 Correct 24 ms 36044 KB Output is correct
11 Correct 23 ms 36084 KB Output is correct
12 Correct 43 ms 36120 KB Output is correct
13 Correct 61 ms 36120 KB Output is correct
14 Correct 27 ms 36004 KB Output is correct
15 Correct 71 ms 36024 KB Output is correct
16 Correct 20 ms 36132 KB Output is correct
17 Correct 36 ms 36088 KB Output is correct
18 Correct 171 ms 36156 KB Output is correct
19 Correct 277 ms 36128 KB Output is correct
20 Correct 334 ms 36132 KB Output is correct