Submission #294024

#TimeUsernameProblemLanguageResultExecution timeMemory
294024kshitij_sodaniRaisins (IOI09_raisins)C++14
100 / 100
997 ms26056 KiB
#include <bits/stdc++.h> using namespace std; #define a first #define b second #define pb push_back typedef long long llo; int n,m; int it[51][51]; int dp[51][51][51][51]; int find(int i,int j,int k,int l){ if(dp[i][j][k][l]>-1){ return dp[i][j][k][l]; } dp[i][j][k][l]=0; for(int ii=i;ii<=k;ii++){ for(int jj=j;jj<=l;jj++){ dp[i][j][k][l]+=it[ii][jj]; } } int ma=1e9; for(int ii=i;ii<k;ii++){ ma=min(ma,find(i,j,ii,l)+find(ii+1,j,k,l)); } for(int jj=j;jj<l;jj++){ ma=min(ma,find(i,j,k,jj)+find(i,jj+1,k,l)); } dp[i][j][k][l]+=ma; return dp[i][j][k][l]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>it[i][j]; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ for(int k=0;k<n;k++){ for(int l=0;l<m;l++){ dp[i][j][k][l]=-1; if(i==k and j==l){ dp[i][j][k][l]=0; } } } } } cout<<find(0,0,n-1,m-1)<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...