CSIE - Mini Programming - Homework #1 - Solved

Ada, a CSIE student, is also an amateur songwriter. She recently writes a wonderful song consisting of N bars. To make this song more popular, she decides to cooperate with a record label.

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.


Fortunately, Ada also knows how a demo is rated in a record label. As humans are biased, the first impression and the ending of a demo may weigh differently in one’s mind. More specifically, given x,y,z from the record label, if the `-th bar, (` + 1)-th bar, ..., and the r-th bar of the song are submitted as the demo, its rating will be

 

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.