oj.uz

Submission #547654

# Submission time Handle Problem Language Result Execution time Memory
547654 2022-04-11T07:42:51 Z chirathnirodha Raisins (IOI09_raisins) C++17
100 / 100
 180 ms 49288 KB 
//Coded by Chirath Nirodha
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define I insert
#define P push
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_tree;
const ll mod=1e9+7;
inline void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
ll n,m;
ll ras[50][50];
ll dp[50][50][50][50];
ll rassum[50][50];
void calc(int x1,int y1,int x2,int y2){
    if(x1==x2 && y1==y2){dp[x1][y1][x2][y2]=0;return;}
    ll temp=INT64_MAX;
    ll sum=0;
    for(int i=x1;i<x2;i++){
        sum+=rassum[i][y2];
        if(y1>0)sum-=rassum[i][y1-1];
        if(dp[x1][y1][i][y2]==-1)calc(x1,y1,i,y2);
        if(dp[i+1][y1][x2][y2]==-1)calc(i+1,y1,x2,y2);
        temp=min(temp,dp[x1][y1][i][y2]+dp[i+1][y1][x2][y2]);
    }
    sum+=rassum[x2][y2];
    if(y1>0)sum-=rassum[x2][y1-1];
    for(int i=y1;i<y2;i++){
        if(dp[x1][y1][x2][i]==-1)calc(x1,y1,x2,i);
        if(dp[x1][i+1][x2][y2]==-1)calc(x1,i+1,x2,y2);
        temp=min(temp,dp[x1][y1][x2][i]+dp[x1][i+1][x2][y2]);
    }
    dp[x1][y1][x2][y2]=temp+sum;
}
void solve(){
    io();
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>ras[i][j];
            rassum[i][j]=ras[i][j];
            if(j>0)rassum[i][j]+=rassum[i][j-1];
        }
    }
    memset(dp,-1,sizeof(dp));
    calc(0,0,n-1,m-1);
    cout<<dp[0][0][n-1][m-1]<<endl;
}
int main(){
    io();
    solve();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 49240 KB Output is correct
2 Correct 20 ms 49172 KB Output is correct
3 Correct 23 ms 49164 KB Output is correct
4 Correct 21 ms 49248 KB Output is correct
5 Correct 23 ms 49156 KB Output is correct
6 Correct 20 ms 49236 KB Output is correct
7 Correct 23 ms 49220 KB Output is correct
8 Correct 21 ms 49224 KB Output is correct
9 Correct 24 ms 49200 KB Output is correct
10 Correct 30 ms 49212 KB Output is correct
11 Correct 28 ms 49224 KB Output is correct
12 Correct 35 ms 49236 KB Output is correct
13 Correct 45 ms 49236 KB Output is correct
14 Correct 27 ms 49260 KB Output is correct
15 Correct 47 ms 49272 KB Output is correct
16 Correct 23 ms 49236 KB Output is correct
17 Correct 32 ms 49184 KB Output is correct
18 Correct 115 ms 49280 KB Output is correct
19 Correct 153 ms 49288 KB Output is correct
20 Correct 180 ms 49284 KB Output is correct