Submission #542932

#TimeUsernameProblemLanguageResultExecution timeMemory
542932Sho10Raisins (IOI09_raisins)C++17
30 / 100
52 ms30676 KiB
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho using ll=long long; using ld=long double; int const INF=1000000005; ll const LINF=1000000000000000005; ll const mod=1000000007; ld const PI=3.14159265359; #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #define f first #define s second #define pb push_back #define mp make_pair #define endl '\n' #define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; ll n,m,dp[55][55][55][55],a[55][55]; void solve(ll xl,ll xr,ll yl,ll yr){ if(xl>xr){ return; } if(yl>yr){ return; } if(xl==xr&&yl==yr){ dp[xl][xr][yl][yr]=0; return; } if(dp[xl][xr][yl][yr]!=LINF){ return; } ll sum=0; for(ll i=xl;i<=xr;i++) { for(ll j=yl;j<=yr;j++) { sum+=a[i][j]; } } for(ll i=xl+1;i<=xr;i++) { solve(xl,i-1,yl,yr); solve(i,xr,yl,yr); dp[xl][xr][yl][yr]=min(dp[xl][xr][yl][yr],dp[xl][i-1][yl][yr]+dp[i][xr][yl][yr]); } for(ll i=yl+1;i<=yr;i++) { solve(xl,xr,yl,i-1); solve(xr,xr,i,yr); dp[xl][xr][yl][yr]=min(dp[xl][xr][yl][yr],dp[xl][xr][yl][i-1]+dp[xl][xr][i][yr]); } dp[xl][xr][yl][yr]+=sum; } int32_t main(){ CODE_START; cin>>n>>m; for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) { cin>>a[i][j]; } } for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) { for(ll i1=i;i1<=n;i1++) for(ll j1=j;j1<=m;j1++) { dp[i][i1][j][j1]=LINF; } } } solve(1,n,1,m); cout<<dp[1][n][1][m]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...