eolymp
bolt
Try our new interface for solving problems
Məsələlər

Компьютерная игра - квадратичные прыжки

Компьютерная игра - квадратичные прыжки

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем трудностей при решении этой задачи это создать не должно.

Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой нибуть герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться с одного края экрана до другого. При этом, при прыжке с одной платформы на соседнюю, у героя уходит |y_2-y_1|^2 энергии, где y_2 и y_1 - высоты, на которых расположены эти платформы. Кроме того у героя есть суперприём, который позволяет перескочить через платформу, но на это затрачивается 3·|y_2-y_1|^2 единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

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