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

Platforms

Platforms

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

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

Giriş verilənləri

Сначала задано количество платформ N (2N50000), затем N чисел в диапазоне от –2000 до +2000 каждое — высоты этих платформ.

Çıxış verilənləri

Вывести в единственной строке два разделенных пробелом целых числа — минимальные необходимые затраты энергии для первой версии игры и для другой версии игры.

Примечание: Для первой версии оказывается выгоднее прыгать по всем подряд платформам 02011, суммарные затраты 20+9=29. Для второй — перепрыгнуть сразу 011 выгоднее (3·11^2=363), чем прыгать по всем платформам подряд (20^2+9^2=481).

Nümunə

Giriş verilənləri #1
3 0 20 11
Çıxış verilənləri #1
29 363