fork download
copy 
  1. /*
  2. (x) (x)
  3. \____/
  4. */
  5. //powmod , sieve , isprime , oset
  6. #define _CRT_SECURE_NO_WARNINGS
  7. #include <iostream>
  8. #include <cstring>
  9. #include <algorithm>
  10. #include <cmath>
  11. #include <vector>
  12. #include <map>
  13. #include <numeric>
  14. #include <queue>
  15. using namespace std;
  16. #define ll long long
  17. int h,w; //\n
  18. int arr[110][110] , dp[110][110] ;
  19.  
  20. int max_phath(int i,int j){
  21.     if(i==h){
  22.         return 0;
  23.     }
  24.  
  25.     if(dp[i][j]!=-1)return dp[i][j];
  26.  
  27.     int res = 0;
  28.     for(int l=-1;l<=1;l++){
  29.         if(j+l>=0 && j+l<w)res = max(res,max_phath(i+1,j+l)+arr[i][j]);
  30.     }
  31.     dp[i][j] = res;
  32.     return res;
  33. }
  34.  
  35. void solve(){
  36.     cin>>h>>w;
  37.     for(int i=0;i<h;i++){
  38.         for(int j=0;j<w;j++){
  39.             cin>>arr[i][j];
  40.         }
  41.     }
  42.     memset(dp,-1,sizeof(dp));
  43.     int ans = 0;
  44.     for(int j=0;j<w;j++){
  45.         ans = max(ans,max_phath(0,j));
  46.  
  47.     }
  48.     cout<<ans <<'\n';
  49.     return;
  50.  
  51. }
  52.  
  53. int main(){
  54.     // ios :: sync_with_stdio(0); cin.tie(0);
  55.     int t; cin >> t;
  56.     for(int k = 0;k<t;k++){
  57.         solve();
  58.     }
  59.     return 0;
  60.     cout<<"88888";
  61. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
1
6 5
3 1 7 4 2
2 1 3 1 1
1 2 2 1 8
2 2 1 5 3
2 1 4 4 4
5 2 7 5 1
stdout
copy 
32
https://ideone.com/DxTpI9
language:
C++14 (gcc 8.3)
created:
1 day 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!