e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

Dijkstra algorithm

Математические платформы

В старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой нибуть герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться с одного края экрана до другого. Игрок может прыгнуть с любой платформы i на любую платформу k, затратив при этом (i - k) * (i - k) * (yi - yk) * (yi - yk) единиц энергии, где yi и yk - высоты на которых расположены эти платформы. Конечно же, энергию следует расходовать максимально экономно.

Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней?

Входные данные

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

Выходные данные

Выведите единственное число - минимальное количество энергии, которое должен потратить игрок на преодоление платформ.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
1 2 3 30
Çıxış verilənləri #1
731
Müəllif Илья Порублёв
Mənbə Летняя школа Севастополь 2013, Волна 1, День 2