Submission #798161

#TimeUsernameProblemLanguageResultExecution timeMemory
798161Mouad_oujRaisins (IOI09_raisins)C++17
5 / 100
5068 ms53344 KiB
#include<bits/stdc++.h> #define int long long using namespace std; int tab[51][51]; int memo[51][51][51][51]; int solve(int xmin,int xmax,int ymin,int ymax) { int ans=10000000000000000,cur=0; for(int x=xmin;x<=xmax;x++) { for(int y=ymin;y<=ymax;y++) cur+=tab[x][y]; } if((xmax-xmin==1 && ymax-ymin==0)||(xmax-xmin==0 && ymax-ymin==1)||(ymax-ymin==0 && xmax-xmin==0)) return cur; if(memo[xmin][xmax][ymin][ymax]!=-1) return memo[xmin][xmax][ymin][ymax]; for(int x=xmin+1;x<=xmax;x++) ans=min(ans,solve(xmin,x-1,ymin,ymax)+solve(x,xmax,ymin,ymax)+cur); for(int y=ymin+1;y<=ymax;y++) ans=min(ans,solve(xmin,xmax,ymin,y-1)+solve(xmin,xmax,y,ymax)+cur); memo[xmin][xmax][ymin][ymax]=ans; return ans; } signed main() { memset(memo,-1,sizeof(memo)); int n,m; cin>>n>>m; for(int x=0;x<n;x++) { for(int y=0;y<m;y++) cin>>tab[x][y]; } cout<<solve(0,n-1,0,m-1); }
#Verdict Execution timeMemoryGrader output
Fetching results...