Codeforces 674C Levels and Regions - CHT Combination

The transition $dp_{\lambda}[i] = \min_{p}(dp_{\lambda}[p] + cost(p+1, i) + \lambda)$ often has structure that allows further improvement with Convex Hull Trick (covered in Section $16$).

If $cost(p+1, i)$ can be written as $A[p] \cdot B[i] + C[p] + D[i]$ (separable into terms depending only on $p$ and terms depending only on $i$), CHT applies. Each transition becomes a line query.

This problem achieves $O(n \log n \log C)$ by combining Aliens Trick with CHT. First Aliens removes the $k$ dimension, then CHT speeds up the $O(n^2)$ transitions to $O(n \log n)$. The techniques compose beautifully.