Problem : 236 - Commando

Problem Statistics

Solved Member: 14　　Submission: 57　　User Tried: 14

Statement:

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

每個士兵 i 都有其戰鬥力評分x_i。原先，每個突擊單位的戰鬥力總和為x，其計算方式是將每位士兵的戰鬥力相加，也就是說，x = x_i + x_i+1 + ... + x_i+k。然而，過去輝煌勝利的經驗告訴你，一個突擊單位的戰鬥力總和應該修正為：修正戰鬥力x'，其計算公式為 x' = ax²+bx+c，而a, b, c是已知係數(其中a<0)，x是這個單位的原本戰鬥力。

身為一個司令官，你的任務就是將士兵們分配成數個突擊單位，確保所有單位的修正戰鬥力總和為最大值。

假設你有4個士兵，x₁ = 2, x₂ = 2, x₃ = 3, x₄ = 4。接著，藉由公式的係數改變該單位的戰鬥力，其中係數a = −1, b = 10, c = −20。

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

Input:Output:

輸入共有三列，第一列包含一個正整數 n，也就是所有士兵總數。

第二列包含3個整數 a, b 和 c，為公式中為了調整突擊部隊戰鬥力的係數。

最後一列包含 n 個整數x₁, x₂, ... , x_n，以空格隔開，分別代表著第一位士兵、第二位士兵、到第 n 位士兵。

• 在 20% 的測試案例中，n ≦ 1000;
• 在 50% 的測試案例中，n ≦ 10, 000;
• 在100% 的測試案例中，n ≦ 1, 000, 000, −5 ≦ a ≦ −1, |b| ≦ 10, 000, 000, |c| ≦ 10, 000, 000 and 1 ≦ x_i≦ 100.

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

Sample Input:Sample Output:

4
-1 10 -20
2 2 3 4

Source:

APIO 2010

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1500ms	65536kb	10
2	1500ms	65536kb	10
3	1500ms	65536kb	10
4	1500ms	65536kb	10
5	1500ms	65536kb	10
6	1500ms	65536kb	10
7	1500ms	65536kb	10
8	1500ms	65536kb	10
9	1500ms	65536kb	10
10	1500ms	65536kb	10