TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

31.0% (18/58)

Tags

Description

原題(其實我是個連結喔

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

每個士兵 $i$都有其戰鬥力評分 $x_i$。原先,每個突擊單位的戰鬥力總和為 $X$,
其計算方式是將每位士兵的戰鬥力相加,也就是說,$X = \sum\limits_{j=i}^{i+k} x_j$。
然而,過去輝煌勝利的經驗告訴你,一個突擊單位的戰鬥力總和應該修正為修正戰鬥力 $X'$,
其計算公式為 $X' = aX^2 + bX + c$,而 $a,b,c$是已知係數($a < 0$),$X$是這個單位的原本戰鬥力。
身為一個司令官,你的任務就是將士兵們分配成數個突擊單位,確保所有單位的修正戰鬥力總和為最大值。

Input Format

$n$

$a$ $b$ $c$

$x_1$ $x_2$ $x_3$ $...$ $x_n$

Input Limits:

$1 \leq n \leq 10^6$

$-5 \leq a \leq -1$

$|b|, |c| \leq 10^6$

$\forall i, |x_i| \leq 100$

對於測資1~8, $n \leq 1000$

Output Format

輸出一整數表示答案

Sample Input 1

4
-1 10 -20
2 2 3 4

Sample Output 1

9

Sample Input 2

4
-2 3 4
4 -3 -2 3

Sample Output 2

10

Hints

Problem Source

改自APIO'10

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1500 250000 250000 65536
1 1500 250000 250000 65536
2 1500 250000 250000 65536
3 1500 250000 250000 65536
4 1500 250000 250000 65536
5 1500 250000 250000 65536
6 1500 250000 250000 65536
7 1500 250000 250000 65536
8 1500 250000 250000 65536
9 1500 250000 250000 65536
10 1500 250000 250000 65536
11 1500 250000 250000 65536
12 1500 250000 250000 65536
13 1500 250000 250000 65536
14 1500 250000 250000 65536
15 1500 250000 250000 65536
16 1500 250000 250000 65536
17 1500 250000 250000 65536
18 1500 250000 250000 65536
19 1500 250000 250000 65536