Qwan Under Attack
All submissions for this problem are available.
The Wizard kingdom of Qwan is being attacked by the Elves of Preslay. Since supplies are limited, the king would like to make the minimum use of their super weapon Avada. Avada missiles are launched with the help of a computer system that makes the judgement of the power level of the enemy soldiers and then allows the king to choose which soldiers to kill. Each missile kills one soldier. The Elf soldiers approach the kingdom in a single line. A group is a series of soldiers such that no two soldiers have a soldier who is not in the group between them. The power of a group is the sum of power of individual soldiers. Since it is a full moon night on the 13th of Friday, the Protective Blessing of Qwert is active. This means that if the maximum powered group is killed, all other soldiers attacking also die of heart attack. You as the Chief Strategist of Qwan have to find the minimum number of Avada missiles that need to be fired.
The first line is a single integer T which is the number of testcases. First line of each testcase will be a single integer N which represent the number of soldiers. The second line will have N space separated integers, Ai representing the power level of the soldiers in the order that they have in the attack formation.
For each testcase output a single line having the minimum number of missiles that need to be launched.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 1000
- 1 ≤ Ai ≤ 5 X 105
Input: 2 5 1 2 3 -1 -4 6 1 1 2 -5 3 0 Output: 3 3
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions