fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long int ll ; 
  5. ll dp[100000+5][5][5];
  6.  
  7. ll mxi(ll x,ll y,ll z){
  8.  
  9.  
  10.     return max(x,max(y,z));
  11.  
  12. }
  13.  
  14. ll mx(ll x,ll y,ll z,ll g){
  15.  
  16.     return max(max(x,g),max(y,z));
  17. }
  18.  
  19. int main() {
  20.  
  21.     ll n=50;
  22.     vector<ll>b={17, -3, 25, -11, 8, -19, 13, -7, 22, -5, 9, -14, 6, -18, 20, -2, 11, -9, 4, -16,
  23.      15, -6, 23, -12, 7, -20, 18, -1, 10, -13, 5, -17, 21, -4, 14, -8, 3, -15, 19, -10,
  24.      2, -21, 16, -22, 24, -23, 1, -24, 12, -25};
  25.     vector<ll>d={-10, 21, -5, 14, -18, 6, -12, 25, -3, 9, -7, 20, -2, 11, -16, 4, -13, 22, -8, 5,
  26.      -19, 7, -1, 18, -6, 23, -4, 15, -11, 2, -20, 8, -9, 17, -14, 3, -21, 10, -15, 24,
  27.      -22, 12, -17, 1, -23, 13, -24, 16, -25, 19};
  28.  
  29.  
  30.     //base-cases
  31.     dp[1][1][1] = b[1] ; 
  32.     dp[1][1][2] = b[1] ; 
  33.     dp[1][2][1] = d[1] ; 
  34.     dp[1][2][2] = d[1] ; 
  35.  
  36.  
  37.     //dp[index][][]
  38.  
  39.  
  40.    int i = 2 ; 
  41.     while(i<=n){
  42.  
  43.         dp[i][1][1] = b[i] + b[i-1] + max(dp[i-2][2][2],dp[i-2][2][1]);
  44.         dp[i][1][2] = b[i] + d[i-1] + mxi(dp[i-2][1][1],dp[i-2][1][2],dp[i-2][2][1]);
  45.         dp[i][2][1] = d[i] + b[i-1] + mxi(dp[i-2][2][1],dp[i-2][2][2],dp[i-2][1][2]);
  46.         dp[i][2][2] = d[i] + d[i-1] + max(dp[i-2][1][2],dp[i-2][1][1]);
  47.  
  48.         i++;
  49.     }
  50.  
  51.     cout<<mx(dp[n][1][1],dp[n][1][2],dp[n][2][2],dp[n][2][1]); 
  52.  
  53.  
  54.  
  55.  
  56.  
  57.     return 0 ; 
  58. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
633
https://ideone.com/G1EOSI
language:
C++14 (clang 8.0)
created:
3 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!