你是一位擁有由 $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$是這個單位的原本戰鬥力。
身為一個司令官,你的任務就是將士兵們分配成數個突擊單位,確保所有單位的修正戰鬥力總和為最大值。
$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$
輸出一整數表示答案
No. | Testdata Range | Score |
---|