TopCoder

detaomega
Omega

User's AC Ratio

92.6% (113/122)

Submission's AC Ratio

33.7% (209/621)

Tags

Description

你是一位擁有由 n 個士兵組成的部隊司令官,而士兵的編號為 1n
為了即將到來的戰役,你計畫將這 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

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

Input Format

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

  • 在 20% 的測試案例中,n1000
  • 在 50% 的測試案例中,n10000
  • 在 100% 的測試案例中,n10000005a1,|b|10000000,|c|10000000,1xi100

Output Format

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

Sample Input 1

4
-1 10 -20
2 2 3 4

Sample Output 1

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 (VSS, 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