2016-17 Woburn Challenge Finals Round - Senior Division
Problem 1: Cow-Bot Construction
It would seem that war is inevitable. Bo Vine's communication with his cow spy has been intercepted by the devious monkeys, confirming his suspicions that the Head Monkey is up to no good! In preparation for the impending conflict with the monkeys, Bo Vine has ordered the construction of a new, state-of-the-art Cow-Bot model from scratch.
The schematics call for N (1 ≤ N ≤ 200,000) different modules to be installed, in any order. Bo Vine's cow engineers require E (1 ≤ E ≤ 10,000) minutes to install any single module. However, the Cow-Bot (being a sophisticated, artificially intelligent piece of hardware) may also be able to help out! If at least Mi (0 ≤ Mi ≤ N) different modules have already been installed into the Cow-Bot up to a certain point in time, then it becomes able to install the i-th module into itself in B (1 ≤ B ≤ 10,000) minutes. Only one module may be in the process of being installed into the Cow-Bot at any time, meaning that the engineers and Cow-Bot may not simultaneously install two different modules at once.
Please help the cows determine the minimum amount of time required for all N modules to be installed into the Cow-Bot.
In test cases worth 7/9 of the points, N ≤ 2000.
Input Format
The first line of input consists of three space-separated integers N, E, and B.
N lines follow, the i-th of which consists of a single integer Mi (for i = 1..N).
Output Format
Output one line consisting of a single integer – the minimum number of minutes required for all N modules to be installed into the Cow-Bot.
Sample Input
7 7 4 4 0 4 2 6 4 4
Sample Output
34
Sample Explanation
One optimal sequence of module installations is as follows (with each step's completion time indicated):
- Module 2 by the Cow-Bot (4 minutes)
- Module 3 by the engineers (11 minutes)
- Module 7 by the engineers (18 minutes)
- Module 4 by the Cow-Bot (22 minutes)
- Module 6 by the Cow-Bot (26 minutes)
- Module 1 by the Cow-Bot (30 minutes)
- Module 5 by the Cow-Bot (34 minutes)
All Submissions
Best Solutions
Point Value: 7 (partial)
Time Limit: 3.00s
Memory Limit: 32M
Added: May 07, 2017
Author: SourSpinach
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)