# CSIE Mini Programming Homework #1 Solved

35.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

## Description

Rate this product

## 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 official 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 specified 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 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

## 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.