Educational DP Contest Z Flog 3
https://atcoder.jp/contests/dp/tasks/dp_z
It is convex hull trick. There are two ways to understrand CHT, the one is using lines, another is using points.
We are given N points (a[i], b[i]) on the a-b plain. And then given $x$, please find the maximum value of $a_i x + b_i$ and find what point gives such a maximum. CHT is used in such a problem. Since $\mathrm{grad} (ax+b)=(x,1)$, we move toward the direction $(x,1)$, the value increases. For example $x=1$, the gradient is as follows.
Therefore, the most farthest point in direction $(x,1)$ gives the maximum. This point must be on the convex hull, so we move on the convex hull, finally find the answer. In this phase, we can use binary search.
By the way, we can generalize CHT. Given $x$ and $y$, please find the maximum of $a_i x + b_i $.
