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
stdin
2 6
8 6 9 1 2 0
1 0 0 1 1 1
stdout
30