Канатная дорога Каракола
В горнолыжном комплексе Каракол строят канатную дорогу. Вдоль трассы стоят 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]; прямые добавляются в порядке убывания наклона (выпуклая оболочка прямых).
Комментарии