Tasks:
 
Task DescriptionDiscussion (0)
Task :: APIO - 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 = xi + xi+1 + · · · + xi+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 x0 is computed by using the equation x0 = 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, x1 = 2, x2 = 2, x3 = 3, x4 = 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:
The input 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.

OUTPUT:
A single line with an integer indicating the maximum adjusted effectiveness achievable.

Constraints
• In 20% of the test cases, n <= 1000;
• In 50% of the test cases, n <= 10, 000;
• In 100% of the test cases, n <= 1, 000, 000, −5 <= a <= −1, |b| <=
10, 000, 000, |c| <= 10, 000, 000 and 1 <= xi <= 100.


Input:
4
-1 10 -20
2 2 3 4

Output:
9

Submit Solution
:
:
Available Languages
Task info
Name:APIO - Commando
Time:0.5 sec.
Memory:64 MB
#Tests:10
AddedBy: harta01
Source:APIO 2010
Task Ratings
Difficulty:

5 (8 votes)
Quality:

4 (8 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
rais.fathin38 0.201 s.
mRilchi 0.45 s.
CodeBreaker 0.495 s.
lawrenceli 0.507 s.
Delsius 0.526 s.
Sarkin 0.532 s.
nfs420 0.532 s.
vjudge1 0.54 s.
yafithekid 0.541 s.
1010011010 0.544 s.
Solved By