fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int s[102][102],dp[102][102];     
  5.  
  6. int main(){
  7.  
  8.   int h,w;            
  9.   cin>>w>>h;
  10.   for(int i=0;i<w;i++){
  11.     for(int j=0;j<h;j++){
  12.     	cin>>s[j][i];
  13.     }
  14.   }
  15.   for(int i=0;i<w;i++)
  16.     dp[0][i]=s[0][i];         
  17.   for(int i=1;i<h;i++){
  18.     for(int j=0;j<w;j++){
  19.       if(j==0){
  20.         dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+s[i][j];
  21.       }
  22.       else if(j==w-1){
  23.         dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+s[i][j];
  24.       }
  25.       else{
  26.         dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-1],dp[i-1][j+1]))+s[i][j];  
  27.       }
  28.     }
  29.   }
  30.  
  31.  
  32.   int maxx=-1;
  33.  
  34.   for(int i=0;i<w;i++){
  35.     if(maxx<dp[h-1][i])            
  36.       maxx=dp[h-1][i];
  37.   }
  38.   cout<<maxx<<"\n";
  39.  
  40.   return 0;
  41. }
Success #stdin #stdout 0s 5536KB
comments (?)
stdin
copy 
3
6
2 6 3 8 7 2
5 3 4 3 3 2
7 9 6 8 7 2
stdout
copy 
39
https://ideone.com/PMOlUq
language:
C++ (gcc 8.3)
created:
2 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!