Изменения

Convex hull trick

68 байт добавлено, 19:17, 23 ноября 2016

→‎Р.Реализация

if (i < n - 1) // если у нас добавляется НЕ последняя прямая,

K[i] = b[i]

B[i] = dp[i] ll x = -inf while (1) { j = st[sz - 1] x = divide(B[j] - B[i], K[i] - K[j]) if (x > from[sz - 1]) break } --sz }

st[sz] = i

from[sz++] = x

Анонимный участник