10500: Covered Walkway


Відправити розв'язок

Бали: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Brain****, C, C++, Java, Pascal, Python, v8js

На прямій задано \(N\) точок з цілими координатами.
Необхідно покрити ці точки відрізками.
Вартість покриття відрізку між точками з координатами \(Xj,Xi\) дорівнює \((Xi-Xj)^2 + C\)
Також дозволяється покривати відрізком лише 1 точку.

Формат вхідних даних

В першому рядку два цілих числа \(N,C\) (\(1 \le N \le 10^6\) , \(1 \le C \le 10^9\))
В другому рядку \(N\) цілих чисел \(Xi\) в порядку зростання - координати точок. (\(1 \le Xi \le 10^9\))

Формат вихідних даних

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

Приклад вхідних даних

10 5000
1
23
45
67
101
124
560
789
990
1019

Приклад вихідних даних

30726

Джерело: The University of Chicago Invitational Programming Contest 2012


Коментарі

Ще немає коментарів.