fork(1) download
  1. #include<iostream>
  2. using namespace std;
  3. int a[200][200],H,W;
  4. int solve(int ax,int ay,int bx,int by){
  5. int maxn=0;
  6. if(ax<H-1 && bx<H-1){int B=0;if(ax!=bx || ay!=by){B=a[bx][by];}maxn=max(maxn,solve(ax+1,ay,bx+1,by)+a[ax][ay]+B);}
  7. if(ay<W-1 && bx<H-1){int B=0;if(ax!=bx || ay!=by){B=a[bx][by];}maxn=max(maxn,solve(ax,ay+1,bx+1,by)+a[ax][ay]+B);}
  8. if(ax<H-1 && by<W-1){int B=0;if(ax!=bx || ay!=by){B=a[bx][by];}maxn=max(maxn,solve(ax+1,ay,bx,by+1)+a[ax][ay]+B);}
  9. if(ay<W-1 && by<W-1){int B=0;if(ax!=bx || ay!=by){B=a[bx][by];}maxn=max(maxn,solve(ax,ay+1,bx,by+1)+a[ax][ay]+B);}
  10. //cout<<ax<<' '<<ay<<' '<<bx<<' '<<by<<' '<<maxn<<endl;
  11. return maxn;
  12. }
  13. int main(){
  14. cin>>H>>W;for(int i=0;i<H;i++){for(int j=0;j<W;j++)cin>>a[i][j];}
  15. cout<<solve(0,0,0,0)+a[H-1][W-1]<<endl;
  16. return 0;
  17. }
Success #stdin #stdout 0s 3628KB
stdin
2 6
8 6 9 1 2 0
1 0 0 1 1 1
stdout
30