fork(1) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int dp[40][40][40][40],H,W,a[40][40];
  5. int main(){
  6. 	cin>>H>>W;
  7. 	for(int i=0;i<H;i++){for(int j=0;j<W;j++){cin>>a[i][j];}}
  8. 	dp[0][0][0][0]=a[0][0];
  9. 	for(int i=0;i<H;i++){
  10. 		for(int j=0;j<W;j++){
  11. 			for(int k=0;k<H;k++){
  12. 				for(int l=0;l<W;l++){
  13. 					if(i+1==k+1 && j==l){dp[i+1][j][k+1][l]=max(dp[i+1][j][k+1][l],dp[i][j][k][l]+a[i+1][j]);}
  14. 					if(i+1==k && j==l+1){dp[i+1][j][k][l+1]=max(dp[i+1][j][k][l+1],dp[i][j][k][l]+a[i+1][j]);}
  15. 					if(i==k+1 && j+1==l){dp[i][j+1][k+1][l]=max(dp[i][j+1][k+1][l],dp[i][j][k][l]+a[i][j+1]);}
  16. 					if(i==k && j+1==l+1){dp[i][j+1][k][l+1]=max(dp[i][j+1][k][l+1],dp[i][j][k][l]+a[i][j+1]);}
  17. 					if(i+1!=k+1 || j!=l){dp[i+1][j][k+1][l]=max(dp[i+1][j][k+1][l],dp[i][j][k][l]+a[i+1][j]+a[k+1][l]);}
  18. 					if(i+1!=k || j!=l+1){dp[i+1][j][k][l+1]=max(dp[i+1][j][k][l+1],dp[i][j][k][l]+a[i+1][j]+a[k][l+1]);}
  19. 					if(i!=k+1 || j+1!=l){dp[i][j+1][k+1][l]=max(dp[i][j+1][k+1][l],dp[i][j][k][l]+a[i][j+1]+a[k+1][l]);}
  20. 					if(i!=k || j+1!=l+1){dp[i][j+1][k][l+1]=max(dp[i][j+1][k][l+1],dp[i][j][k][l]+a[i][j+1]+a[k][l+1]);}
  21. 				}
  22. 			}
  23. 		}
  24. 	}
  25. 	cout<<dp[H-1][W-1][H-1][W-1]<<endl;
  26. 	return 0;
  27. }
Success #stdin #stdout 0s 13480KB
comments (?)
stdin
copy 
2 6
8 6 9 1 2 0
1 0 0 1 1 1
stdout
copy 
30
https://ideone.com/u8S55J
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!