Ada’s Demo Album
Problem Description
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.
Before making an o cial submission, she has done some surveys in order to pick and present the best snatch to the record label. With valuable feedbacks and a statistical transformation, for the i-th bar (1 i N), its greatness can be speci ed with a value ai. Note that though Ada’s song is wonderful, ai may be non-positive since a statistical transformation has been applied.
Fortunately, Ada also knows how a demo is rated in a record label. As humans are biased, the rst impression and the ending of a demo may weigh di erently in one’s mind. More speci cally, 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
r 1
X
S = x a‘ + y ak + z ar
k=‘+1
Please help Ada determine which snatch should be picked to achieve the maximal rating.
Input
The rst line of the input contains 4 integers N, x, y, z, denoting the number of bars in the original song and the coe cients 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.
• 2N2105
• 1 x; y; z 104
• 109 ai 109; 8i = 1; 2; : : : ; N
2
Algorithm Design and Analysis (NTU CSIE, Fall 2021)
Mini Programming Homework #1
Test Group 0
(0 %)
Test Group 1 (10 %)
•
Sample Input
• N 2000
Test Group 2
(40 %)
Test Group 3 (50 %)
•
x = y = z
• 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-7050-29
1
10000 100000000
Sample Output 1
Sample Output 2
Sample Output 3
-3
1239
314159265358
Explanation
• In the rst 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 deja vu.
3
