TopCoder

Thumb output jddoia
$\huge 南ことり$
$https://www.ototot.com.tw/TIOJ/ \\我要拿牌、去東京、變紅色,那就努力吧 \\ 確かな今よりも新しい夢つかまえたい$

User's AC Ratio

94.7% (18/19)

Submission's AC Ratio

42.1% (32/76)

Description

你是一位擁有由1到n個士兵的部隊司令官。
為了即將到來的戰役,你計畫將這n個士兵分成數個突擊單位。
為了凝聚士氣,每個單位將由連續序列(如(i, i+1, . . . , i+k)的士兵組成。

每個士兵i都有其戰鬥力評分xi。原先,每個突擊單位的戰鬥力總和為x,
其計算方式是將每位士兵的戰鬥力相加,也就是說,x = xi + xi+1 + ... + xi+k
然而,過去輝煌勝利的經驗告訴你,一個突擊單位的戰鬥力總和應該修正為:
修正戰鬥力x’,其計算公式為 x’ = ax2+bx+c,而a, b, c是已知係數(a<0),x是這個單位的原本戰鬥力。
身為一個司令官,你的任務就是將士兵們分配成數個突擊單位,確保所有單位的修正戰鬥力總和為最大值。

假設你有4個士兵,x1 = 2, x2 = 2, x3 = 3, x4 = 4。
接著,藉由公式的係數改變該單位的戰鬥力,其中係數a = −1, b = 10, c = −20。

既然這樣,最好的方式是將所有士兵分成三個戰鬥單位:
第一個單位包含士兵1和2、第二個單位包含士兵3、第三個單位包含士兵4。
這三個單位的戰鬥力總和將分別為4、3、4,而修正後的戰鬥力總和為4、1、4。
這種分配方式的總修正戰鬥力將為9,而且這是最好的分法。

Input Format

輸入共有三列,第一列包含一個正整數n,也就是所有士兵總數。
第二列包含3個整數a, b,和c,為公式中為了調整突擊部隊戰鬥力的係數。
最後一列包含n個整數x1, x2, ... , xn,以空格隔開,分別代表著第一位士兵、第二位士兵、到第n位士兵。

•在 20% 的測試案例中,n ≦ 1000;
•在 50% 的測試案例中,n ≦ 10000;
•在100% 的測試案例中,n ≦ 1000000,
−5 ≦ a ≦ −1, |b| ≦ 10000000, |c| ≦ 10000000 以及 1 ≦ xi≦ 10

Output Format

以單列整數形式代表可達到之最大修正後的戰鬥力。

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

Hints

Problem Source

原TIOJ1745 / APIO '10

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3500 65536 65536
1 3500 65536 65536
2 3500 65536 65536
3 3500 65536 65536
4 3500 65536 65536
5 3500 65536 65536
6 3500 65536 65536
7 3500 65536 65536
8 3500 65536 65536
9 3500 65536 65536