CodePSU 2019 - Advanced

Start

2019-03-24 09:15 AKDT

CodePSU 2019 - Advanced

End

2019-03-24 13:15 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -671 days 3:28:30

Time elapsed

4:00:00

Time remaining

0:00:00

Problem E
Gym Nut

Everyone knows the real reason why people work out. Not for health reasons, or to maintain one’s youthful and athletic frame, or because it’s fun. People work out excessively because they want to annoy the crap out of everyone by being as condescending as possible about it. Depending on how obsessed one is about working out, different individuals have different aggregate-nuisance, or AG-NU scores.

Most gym nuts don’t realize that this is not actually a good trait, and your buddy Bob is no different. He knows you can code, so he wanted you to devise an algorithm that can help him maximize his AG-NU. Bob does a few different exercises, and each one of them is assigned a different NU score. The total score of all the exercises he does is called an AG-NU score. While it would make sense to just do the exercises with the highest NU scores, but Bob only has so much energy. Bob has a maximum amount of energy that he can spend. If he chooses to do back to back workouts, he loses energy by some cooldown factor. Taking an hour off doesn’t add points to his AG-NU score, but it resets his energy back to his max. This factor is multiplied by the maximum energy he could have spent in the previous workout to determine how much energy he can spend in the next one. Bob gives you a list of exercises that he can do every five minutes, and the maximum possible energy he could spend for each of those workouts. For a given workout, Bob spends as much energy as he can, the minimum of his max energy at the time or the max energy for the exercise.

It’s your job to maximize his AG-NU (equivilant to energy spent) within the constraints of how much energy he has.

Input

There are three lines of input to this program.
Line $1$: Composed of two space-separated integers ($e$ $n$). $e$ ($10 \leq e \leq 10\, 000$) is the amount of energy that this Bob can expend during an exercise, measured in some arbitrary unit of energy. It decreases by a factor of $c$ if Bob chooses to not take a break after the previous workout. $n$ ($1 \leq n \leq 1\, 000$) is the total number of workouts Bob can complete if he completes every one. The energies for the workouts are listed on line $3$. Line $2$: Composed of one real number with up to two decimal places ($c$). $c$ is the cooldown factor mentioned above ($0 \leq c \leq 1$). Line $3$: Composed of $n$ space-separated integers ($1 \leq x \leq 1\, 000$). They represent the exercise available for Bob to do each $5$ minutes. He can decide to do the exercise and gain NU points equal to the lesser of his current max energy or the energy of the exercise, or he can take a break to reset his max energy.

Output

The output is always composed of one line. Line $1$: Bob’s optimal AG-NU value. This is a real number that is correct within a relative or absolute error of $10^{-6}$. It represents the total amount of energy that Bob has expended by completing the optimal workout routine for the given exercises.

Sample Input 1 Sample Output 1
100 4
0.5
100 60 40 20
187.5
Sample Input 2 Sample Output 2
100 4
0.5
50 50 10 50
150.0