DCEPC501  Save Thy Toys
Leonard is very fond of buying rare and expensive science fiction toys. He keeps his collection in a sequential order of the date on which the toy was bought in a special closet so that his roomie Sheldon never gets hold of his toys. But because of his bad luck Leonard once loses a bet to Sheldon and Sheldon demands a share Leonard’s toys. Since Leonard doesn’t want to loose much money, he decides upon a strategy to reduce his loss to minimum.
Leonard, beginning from the first toy in his closet will pick some toys, say "x" toys in sequence. Sheldon will then pick the next "x" toys (Note that Sheldon picks equal no. of toys as picked by Leonard in his move unless the remaining toys are less than "x". In that case he picks all of the remaining). This will keep going on till no more toys are left in the closet for Leonard to pick. You are given the sequence of toys with their price. Help Leonard in maximizing the total price of all toys he picks.
Leonard in his each turn can either pick only 1 or 2 or 3 toys ("x" described above can take value either 1, 2 or 3).
Input
First line specifies T, the number of test cases.
Each test case contains N in the first line. Second line contains N integers as described above.
Output
Output 1 line for each test case giving the maximum possible value of the total sum of all toys Leonard picks.
Constraints
1<=T<=10
1<=N<=100000
1<=Price of toys<=1000000
Example
Input: 2 4 5 4 3 2 6 10 8 7 11 15 20 Output: 12 53
Explanation:
In 1st case, Leonard picks 3 toys in his first move with value 5,4,3 and Sheldon has no choice but to pick the last.
In 2nd case, Leonard picks 10, 8. Then Sheldon picks 7,11. And then Leonard picks the rest.
hide comments
aryan29:
20190608 00:07:56
dp is so difficult 

manjeet_:
20180809 18:44:34
if getting WA .. try using scanf printf and long long int...got accepted in 2nd go 

karan_yadav:
20180705 14:16:57
Simple recursion with a 1D array for memoization and std::ios::sync_with_stdio(false) will do. 0.13s


priyanshu_98:
20180608 21:37:33
Read carefully the lineLeonard in his each turn can either pick only 1 or 2 or 3 toys ("x" described above can take value either 1, 2 or 3).In each turn he can choose 1 or two or three toys.so x in not fixed.In each move you can change the value of x. Last edit: 20180608 21:38:48 

Jas R Mehta:
20180123 13:04:27
use scanf printf instead of cin cout or u will get TLE 

atikahamedutso:
20171224 09:49:50
finally got AC :) 

burninggoku:
20170920 10:40:21
AC in one go gives me more happiness :) :) :) than my girlfriend can ever give me... sad part is i am single :( :( 

mudra03:
20170919 21:28:29
java users TLE :(


mastik5h_1998:
20170919 07:39:16
too much optimisation..... :( 

rohit9934:
20170828 12:40:58
brute force + optimisation = DP 
Added by:  dce coders 
Date:  20120418 
Time limit:  0.310s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C C++ 4.3.2 CPP CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own Problem 