fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long t,n;
  4. const int Nmax=100010;
  5. long long a[Nmax];
  6. long long dp[Nmax];
  7. long long ans(int i){
  8.     if(i>=n)
  9.         return 0;
  10.     if(dp[i]==-1){
  11.     long long x=0,y=0,z=0;
  12.     if(i<n)
  13.         x=a[i]+ans(i+2);
  14.     if(i+1<n)
  15.         y=a[i]+a[i+1]+ans(i+4);
  16.     if(i+2<n)
  17.         z=a[i]+a[i+1]+a[i+2]+ans(i+6);
  18.     return dp[i]=max(x,max(y,z));}
  19.     else return dp[i];
  20. }
  21.  
  22. int main(){
  23.     cin>>t;
  24.     while(t--){
  25.         cin>>n;
  26.         for(int i=0;i<n;i++)
  27.             cin>>a[i];
  28.         memset(dp,-1,sizeof dp);
  29.         cout<<ans(0)<<endl;
  30.     }
  31. }
Success #stdin #stdout 0s 4420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VDtmxO
language:
C++14 (gcc 8.3)
created:
6 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!