DMPG '18 G2 - Gardening Fun

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Bob is working on his biology assignment! He has N plants in a row and needs to water all of them today. Bob wants to water the i^\text{th} plant with v_i milliliters of water. He can spray exactly 1 milliliter of water onto each plant in a contiguous row of length i at a cost of A \cdot i + B where A and B are given positive integers.

Bob is also okay with cutting some corners with his plant project. Specifically, say he ends up watering the i^\text{th} plant with w_i milliliters. Then he will consider C \cdot ((w_1-v_1)^2 + (w_2-v_2)^2 + \dots + (w_N-v_N)^2) as an additional cost, where C is some given positive integer.

Help Bob minimize the sum of these costs!

Constraints

For all subtasks:

0 \le A, B, C \le 100

0 \le v_i \le 100 for all 1 \le i \le N

Subtask 1 [40%]

1 \le N \le 2\,000

Subtask 2 [60%]

1 \le N \le 200\,000

Input Specification

The first line contains a single integer N.
The next line contains three space-separated integers A, B, C in that order.
The final line contains N space-separated integers v_1, v_2, \dots, v_N.

Output Specification

Output a single integer, the minimum possible sum of the costs.

Sample Input 1

5
1 9 8
1 1 0 1 1

Sample Output 1

22

Sample Input 2

8
1 2 100
2 2 0 1 0 1 1 1

Sample Output 2

16

Comments

There are no comments at the moment.