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
Коментарі