Submission #10105

#TimeUsernameProblemLanguageResultExecution timeMemory
10105gs14030On grid (kriii2_O)C++98
1 / 4
1000 ms2212 KiB
#include <cstdio> int n,m,gs[310][310],hs[310][310],gshs[310][310]; int koi(int a,int b) { if(hs[a][b]!=-987654321) return hs[a][b]; int x=0,y=0; if(a==n){ for(int i=b; i<=m; i++) x+=gs[a][i]; return x; } if(b==m){ for(int i=a; i<=n; i++) x+=gs[i][b]; return x; } for(int i=a; i<=n; i++) for(int j=b; j<=m; j++) y+=gs[i][j]; for(int i=a; i<n; i++) for(int j=b; j<m; j++) { x=gshs[i][j]+gshs[a-1][b-1]-gshs[a-1][j]-gshs[i][b-1]; x+=koi(i+1,j+1); if(y<x) y=x; } hs[a][b]=y; return hs[a][b]; } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&gs[i][j]); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) hs[i][j]=-987654321; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) gshs[i][j]+=gs[i][j]+gshs[i-1][j]+gshs[i][j-1]-gshs[i-1][j-1]; printf("%d",koi(1,1)); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...