fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define dd double
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define yes cout << "YES\n"
  8. #define no cout << "NO\n"
  9. #define el "\n"
  10. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define fix(x) cout << fixed << setprecision(x)
  12. #define all(v) v.begin(),v.end()
  13. #define dpp(v,val) memset(v,val,sizeof(v))
  14. #define mod 1e9+7
  15. const int N = 1e5 + 5;
  16. int n,m,mx=0;
  17. vector<vector<int>>v;
  18. int dp[101][101];
  19. int solve(int i,int j)
  20. {
  21.     if(i==n)  return 0;
  22.     if(dp[i][j]!=-1) return dp[i][j];
  23.     int path1=0,path2=0,path3=0;
  24.     if(j-1>=0) path1=solve(i+1,j-1);
  25.                path2=solve(i+1,j);
  26.     if(j+1<m)  path3=solve(i+1,j+1);
  27.     dp[i][j]= v[i][j]+max({path1,path2,path3});
  28.  
  29.     return dp[i][j];
  30. }
  31. void HereWeGoAgain()
  32. {
  33.     cin>>n>>m;
  34.     v.resize(n);
  35.     for(int i=0;i<n;i++)
  36.     v[i].resize(m);
  37.     for(int i=0;i<n;i++) 
  38.     for(int j=0;j<m;j++)
  39.     cin>>v[i][j];
  40.     dpp(dp,-1);
  41.     for(int j=0;j<m;j++)
  42.     mx=max(mx,solve(0,j));
  43.     cout<<mx<<el;
  44. }
  45. int32_t main() 
  46. {
  47.     Arwa
  48.     int t=1;
  49.     cin>>t;
  50.     for(int i=1;i<=t;i++)
  51.     {
  52.     HereWeGoAgain();
  53.     }
  54.     return 0;
  55. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/nK4TLQ
language:
C++ (gcc 8.3)
created:
2 days 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!