APIO10A  Commando
Commando
You are the commander of a troop of n soldiers, numbered from 1 to n. For the battle ahead, you plan to divide these n soldiers into several commando units. To promote unity and boost morale, each unit will consist of a contiguous sequence of soldiers of the form (i, i+1, . . . , i+k).
Each soldier i has a battle effectiveness rating xi . Originally, the battle effectiveness x of a commando unit (i, i+1, . . . , i+k) was computed by adding up the individual battle effectiveness of the soldiers in the unit. In other words, x = x_{i} + x_{i}+1 + · · · + x_{i}+k .
However, years of glorious victories have led you to conclude that the battle effectiveness of a unit should be adjusted as follows: the adjusted effectiveness x is computed by using the equation x = ax^{2} + bx + c, where a,b, c are known coefficients(a < 0), x is the original effectiveness of the unit.
Your task as commander is to divide your soldiers into commando units in order to maximize the sum of the adjusted effectiveness of all the units.
For instance, suppose you have 4 soldiers, x_{1} = 2, x_{2} = 2, x_{3} = 3, x_{4} = 4. Further, let the coefficients for the equation to adjust the battle effectiveness of a unit be a = −1, b = 10, c = −20. In this case, the best solution is to divide the soldiers into three commando units: The first unit contains soldiers 1 and 2, the second unit contains soldier 3, and the third unit contains soldier 4. The battle effectiveness of the three units are 4, 3, 4 respectively, and the
adjusted effectiveness are 4, 1, 4 respectively. The total adjusted effectiveness for this grouping is 9 and it can be checked that no better solution is possible.
Input format:
First Line of input consists number of cases T.
Each case consists of three lines. The first line contains a positive integer n, the total number of soldiers. The second line contains 3 integers a, b, and c, the coefficients for the equation to adjust the battle effectiveness of a commando unit. The last line contains n integers x1 , x2 , . . . , xn , separated by spaces, representing the battle effectiveness of soldiers 1, 2, . . . , n, respectively.
Constraints:
T<=3
n ≤ 1, 000, 000,
−5 ≤ a ≤ −1
b ≤ 10, 000, 000
c ≤ 10, 000, 000
1 ≤ xi ≤ 100.
Output format:
Output each answer in a single line.
Input:
3
4
1 10 20
2 2 3 4
5
1 10 20
1 2 3 4 5
8
2 4 3
100 12 3 4 5 2 4 2
Output:
9
13
19884
(Official dataset of APIO was NOT used in this problem.)
hide comments
kliu31415:
20160508 01:43:12
I have an O(NlogN) C++ solution using the convex hull trick and it runs in 0.7s with getchar_unlocked (barely gets AC). My O(N) solution with a pointer walk runs in 0.44s, so that means that IO makes up most of the run time for this problem. Lesson: Use fast IO on Õ(N) problems. Last edit: 20160508 03:34:16 

margiki:
20160320 09:57:27
How have you passed TLE ? I have an O(N) solution and after test 9 I get TLE :( 

paras meena:
20150105 09:45:22
is there any problem with cluster for out of index i got WA why?? :/ Plz Show SegFault :P 

Alex Abbas:
20130830 17:25:34
Was difficult but convex hull trick should be your 1st guess 

Bidhan:
20130818 19:45:05
Fix the formatting. ax2 should be ax^2 (actual format could not be shown in comment). Last edit: 20130818 01:01:57 
Added by:  Shafaet 
Date:  20130817 
Time limit:  0.300s0.800s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  APIO 2010 