Изменения

Будем хранить 2 массива (имитирующих стеки) : front[] и st[] - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что x[i] = a[i] возрастают (по условию задачи), а значит мы можем искать первое такое j, что x[i] >= front[j] не бинарным поиском, а методом 2х указателей за O(n) суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x.

==Р.Реализация==

from[0] = -∞

sz = 1 // текущий размер выпуклой оболочки

pos = 0 // текущая позиция первго такого j, что x[i] >= front[st[j]]

while (front[pos] < x[i]) ++pos

j = st[pos]

B[i] = dp[i]

ll x = -inf

j = st[sz - 1]

x = divide(B[j] - B[i], K[i] - K[j])

if (x > from[sz - 1]) break

--sz

st[sz] = i

(Здесь функция divide(a, b) возвращает нужное округление a / b)

Такая реализация будет работать за O(n).

==Динамический convex hull trick==

Заметим, что условия на прямые, что k[i] возрастает/убывает и x[i] убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).