e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dynamic Programming - Linear

Подорож із заходу на схід

Є n міст, що стоять на прямій із заходу на схід. Міста пронумеровані від 1 до n, в порядку їх із заходу на схід розміщення. Кожна точка на прямій має свою одновимірну координату, і точка ближче на схід має більшу координату. Координата i-го міста - xi.

Зараз Ви знаходитеся в 1 місті, і хочете відвідати всі міста. У вас є два способи подорожувати:

  • Ходити по прямій. При цьому ваш рівень втоми буде збільшуватися на a одиниць кожен раз, коли Ви будете переміщатися на відстань 1, незалежно від напрямку..
  • Переміщуватися в будь-яку точку, яку хочете. Ваш рівень втоми буде збільшуватися на b одиниць, незалежно від відстані переміщення.

Вхідні дані

Перший рядок містить три числа n n (2n105), a і b (1a, b109). Наступний рядок містить n цілих чисел x1, x2, ... , xn (1xi109). Для всіх i (1in1) має місце нерівність xi < xi+1.

Вихідні дані

Виведіть мінімально можливий рівень втоми, при якому ви відвідаєте всі міста.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 2 5
1 2 5 7
Вихідні дані #1
11
Вхідні дані #2
6 3 7
1 3 6 10 11 13
Вихідні дані #2
29
Вхідні дані #3
7 1 2
24 35 40 68 72 99 103
Вихідні дані #3
12
Автор Rashad Mammadov, Abutalib Namazov
Джерело Azərbaycan 2019: Yuxarı yaş olimpiada hazırlığı qrupuna seçim turu