TopCoder

Thumb 001 870
detaomega
$Omega$

User's AC Ratio

97.5% (78/80)

Submission's AC Ratio

36.8% (145/394)

Description

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

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

假設你有 $4$ 個士兵,$x_1 = 2, x_2 = 2, x_3 = 3, x_4 = 4$。
接著,藉由公式的係數改變該單位的戰鬥力,其中係數 $a = -1, b = 10, c = -20$。

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

Input Format

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

  • 在 20% 的測試案例中,$n ≦ 1000$
  • 在 50% 的測試案例中,$n ≦ 10000$
  • 在 100% 的測試案例中,$n ≦ 1000000$,$-5 \le a \le -1, |b| \le 10000000, |c| \le 10000000, 1 \le x_i \le 100$

Output Format

輸出一個整數,代表可達到最大的修正戰鬥力總和。

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

Hints

2021.04.09 Update: Added $\LaTeX$ and updated constraints by FHVirus

Problem Source

原TIOJ1745 / APIO '10

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3500 65536 262144 1
1 3500 65536 262144 2
2 3500 65536 262144 3
3 3500 65536 262144 4
4 3500 65536 262144 5
5 3500 65536 262144 6
6 3500 65536 262144 7
7 3500 65536 262144 8
8 3500 65536 262144 9
9 3500 65536 262144 10