Submission #798152

#TimeUsernameProblemLanguageResultExecution timeMemory
798152Mouad_oujRaisins (IOI09_raisins)C++17
10 / 100
375 ms53368 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) { if(memo[xmin][xmax][ymin][ymax]!=-1) return memo[xmin][xmax][ymin][ymax]; int ans=1000*50*50*50*51,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)) return cur; 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); }

Compilation message (stderr)

raisins.cpp: In function 'long long int solve(long long int, long long int, long long int, long long int)':
raisins.cpp:10:26: warning: integer overflow in expression of type 'int' results in '2080032704' [-Woverflow]
   10 |     int ans=1000*50*50*50*51,cur=0;
      |             ~~~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...