Mini Programming
Ada’s Demo Album
In order to obtain a recording contract, she has to prepare a demo and submit it to a record label in hopes of being invited to record a full-length album in a professional recording studio. However, as a CSIE sophomore tortured by exploding assignments, she has no time to record an additional demo. Instead, she would like to simply submit a snatch of her N-barred song as a demo. A snatch of a song is valid if both the two following conditions hold:
• It can be obtained by removing several (possibly zero) bars from the beginning and several (possibly zero) bars from the end.
• It consists of at least 2 bars.
Please help Ada determine which snatch should be picked to achieve the maximal rating.
Input
The first line of the input contains 4 integers N, x, y, z, denoting the number of bars in the original song and the coefficients used in rating evaluation.
The second line of the input contains N space-separated integers a1,a2,...,aN, where the i-th integer denotes that greatness of the i-th bar.
• 2 ≤ N ≤ 2 × 105
• 1 ≤ x,y,z ≤ 104
• −109 ≤ ai ≤ 109,∀i = 1,2,...,N
Test Group 0 (0 %)
• Sample Input
Test Group 2 (40 %)
• x = y = z
Test Group 1 (10 %)
• N ≤ 2000
Test Group 3 (50 %)
• No Additional Constraint
Output
Please output an integer S indicating the maximal achievable rating.
Sample Input 1 Sample Input 2 Sample Input 3
6 1 1 1 8 59 4 87 3 5358 5926 3141
-12 7 -127 -1 -2 -7 0 8 -7 0 5 0 -2 9 1 10000 100000000
Sample Output 1 Sample Output 2 Sample Output 3
-3 1239 314159265358
Explanation
• In the first testcase, S achieves its maximum by taking (`,r) = (4,5), S = 1 · (−1) + 1 · (−2) = −3.
• In the second testcase, S achieves its maximum by taking (`,r) = (2,8), S = 59 · 8 + 4 · ((−7) + 0 + 5 + (−2)) + 87 · 9 = 1239.
• In the third testcase, S achieves its maximum by taking (`,r) = (1,3), S = 5358 · 1 + 5926 · 104 + 3141 · 108 = 314159265358.
Hint
Roses are red,
Violets are blue,
See the Test Group 2?
It’s a d´ej`a vu.
