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

Dijkstra algorithm

Математичні платформи

У багатьох старих іграх з двовимірною графікою можна зіткнутись з подібною ситуацією. Який небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. Гравець може стрибннути з довільної платформи i на ловільну платформу k, витративши при цьому (i - k) * (i - k) * (yi - yk) * (yi - yk) одиниць енергії, де yi та yk - висоти, на яких розміщено ці платформи. Звичайно ж, енергію потрібно витрачати максимально економно.

Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?

Вхідні дані

У першому рядку записана кількість платформ n (1n4000). Другий рядок містить n цілих чисел, які не перевищують по модулю 200000 - висоти, на яких розміщено платформи.

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4
1 2 3 30
Вихідні дані #1
731
Автор Илья Порублёв
Джерело Летняя школа Севастополь 2013, Волна 1, День 2