fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long t,n;
  4. const int Nmax=100000+5;
  5. long long a[Nmax];
  6. long long dp[Nmax];
  7. long long ans(int i){
  8.     if(i>=n)
  9.         return 0;
  10.     long long x,y,z;
  11.     if(i<n){
  12.         x=a[i];
  13.         if(i+2<n){
  14.             if(dp[i+2]==-1)
  15.                 dp[i+2]=ans(i+2);
  16.             x+=dp[i+2];
  17.         }
  18.     }
  19.     if(i+1<n){
  20.         y=a[i]+a[i+1];
  21.          if(i+4<n){
  22.             if(dp[i+4]==-1)
  23.                 dp[i+4]=ans(i+4);
  24.             y+=dp[i+4];
  25.         }
  26.     }
  27.     if(i+2<n){
  28.         z=a[i]+a[i+1]+a[i+2];
  29.          if(i+6<n){
  30.             if(dp[i+6]==-1)
  31.                 dp[i+6]=ans(i+6);
  32.             z+=dp[i+6];
  33.         }
  34.     }
  35.     return dp[i]=max(x,max(y,z));
  36. }
  37.  
  38. int main(){
  39.     cin>>t;
  40.     while(t--){
  41.         cin>>n;
  42.         for(int i=0;i<n;i++)
  43.             cin>>a[i];
  44.         memset(dp,-1,sizeof dp);
  45.         cout<<ans(0)<<endl;
  46.     }
  47. }
Success #stdin #stdout 0s 4296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IQsxZ7
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!