DMPG '18 G2 - Gardening Fun

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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!


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

1 9 8
1 1 0 1 1

Sample Output 1


Sample Input 2

1 2 100
2 2 0 1 0 1 1 1

Sample Output 2



There are no comments at the moment.