DMPG '18 G4 - Variation

View as PDF

Submit solution

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

Author:
Problem types

You are given an array of N integers v_1, v_2, \dots, v_N. You can increase any element by 1 at a cost of A or decrease any element by 1 at a cost of B. Determine the minimum cost to make all elements of the array distinct. The values are allowed to be decreased so that they are negative.

Constraints

For all subtasks:

1 \le N \le 2\,000

1 \le A, B \le 1\,000\,000

Subtask 1 [30%]

1 \le v_i \le 2\,000

Subtask 2 [70%]

1 \le v_i \le 1\,000\,000\,000

Input Specification

The first line will contain a single integer, N.
The second line will contain two space-separated integers, A and B in that order.
The third and final line will contain N space-separated integers, v_1, v_2, \dots, v_N.

Output Specification

Output a single integer, the minimum cost required.

Sample Input

5
4 2
6 5 6 6 5

Sample Output

12

Comments

There are no comments at the moment.