fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     vector<int>h={100, 100, -50, -50, -50, -50, -50, -50, 100, 100};
  6.     int n=h.size();
  7.       int ans=-999999;
  8.     vector<vector<int>>dp(n,vector<int>(4,-999999));
  9.     dp[1][2]=h[0]+h[1];
  10.     dp[2][2]=h[1]+h[2];
  11.     dp[2][3]=h[1]+h[2]+h[0];
  12.     dp[3][2]=h[3]+h[2];
  13.     dp[3][3]=h[3]+h[2]+h[1];
  14.     dp[4][2]=h[4]+h[3];
  15.     dp[4][3]=h[4]+h[3]+h[2];
  16.     for(int i=0;i<5;i++){
  17.         ans=max({ans,dp[i][2],dp[i][3]});
  18.     }
  19.     vector<int>a=h;
  20.    int a1=-999999,a2=-999999,a3=ans;
  21.     for(int i=4;i<n;i++){
  22.  
  23.      int a=h[i]+h[i-1];
  24.      int b=h[i]+h[i-1]+h[i-2];
  25.      int s1=-999999,s2=-999999,s3=-999999,s4=-999999;
  26.     // int a1=-999999,a2=-999999;
  27.    //  for(int j=i-3;j>=0;j--){
  28.           s1=a+dp[i-3][2];
  29.          if(i-4>=0)
  30.           s3=a+dp[i-4][3];
  31.           a1=max({a1,s1,s3});
  32.  
  33.     // }
  34.      dp[i][2]=a1;
  35.      //for(int j=i-5;j>=0;j--)
  36.      //{
  37.      if(i-5>=0){
  38.           s2=b+dp[i-5][3];
  39.           s4=b+dp[i-5][2];
  40.      }
  41.          a2=max({a2,s2,s4}); 
  42.     // }
  43.      dp[i][3]=a2; 
  44.      a3=max({a3,a1,a2});
  45.  
  46.     }
  47.     cout<<a3<<endl;
  48.     return 0;
  49. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
300
https://ideone.com/QdLTeJ
language:
C++ (gcc 8.3)
created:
40 minutes 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!