Канатная дорога Каракола


Отправить решение Решать в редакторе

Сложность: 80%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В горнолыжном комплексе Каракол строят канатную дорогу. Вдоль трассы стоят n опор, опора i находится на расстоянии x[i] метров от подножия (x[1] < x[2] < … < x[n]). На первой и последней опоре обязательно будут станции, на любых других — по желанию. Станция на опоре i стоит s[i] сомов (для первой опоры тоже нужно заплатить).

Пролёт каната между соседними станциями на опорах i < j обходится в (x[j] − x[i])² сомов: длинный пролёт требует толстого каната и мощных моторов.

Рисунок

Выберите опоры для станций так, чтобы суммарная стоимость станций и пролётов была наименьшей.

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

В первой строке — число n (2 ≤ n ≤ 5 · 10⁵). Во второй строке — n целых чисел x[i] (0 ≤ x[1] < x[2] < … < x[n] ≤ 10⁹). В третьей строке — n целых чисел s[i] (0 ≤ s[i] ≤ 10¹⁸).

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

Выведите наименьшую стоимость. Гарантируется, что она не превосходит 4 · 10¹⁸.

Пример 1

Вход:

5
0 2 4 5 8
1 9 2 9 1

Выход:

36

Пояснение

Выгодно поставить станции на опорах 1, 3 и 5: стоимость станций 1 + 2 + 1 = 4, пролётов 4² + 4² = 32, всего 36. Если поставить станции на всех опорах, получится 22 + 18 = 40, а только на опорах 1 и 5 — 2 + 8² = 66.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 25 % тестов n ≤ 2000.

Подсказка

dp[j] = s[j] + min_i (dp[i] + x[i]² − 2·x[i]·x[j]) + x[j]² — минимум линейных функций от x[j]; прямые добавляются в порядке убывания наклона (выпуклая оболочка прямых).


Комментарии

Еще нет ни одного комментария.