Изменения
→Р.Реализация
sz = 1 // текущий размер выпуклой оболочки
pos = 0 // текущая позиция первго такого j, что x[i] >= front[st[j]]
for i = 1..n-1 { while (front[pos] < x[i]) ++pos
j = st[pos]
dp[i] = K[j] * a[i] + B[j]
st[sz] = i
from[sz++] = x
}
(Здесь функция divide(a, b) возвращает нужное округление a / b)
Такая реализация будет работать за O(n).
