IOI Aliens - Combined Optimization

Step $1$: Apply Aliens Trick. Add penalty $\lambda$ per photo to remove the $k$ dimension. Now you have $O(n)$ states instead of $O(nk)$. Step $2$: The transition has form $dp_{\lambda}[i] = \min_p(dp_{\lambda}[p] + f(p, i))$ where $f(p, i)$ involves quadratic terms.

Rewrite $f(p, i)$ in the form $m_p \cdot i + b_p$ and apply Convex Hull Trick (from Section $16$). Final complexity: $O(n \log n \log C)$ where $C$ is the coordinate range. The Aliens Trick removes one dimension, and CHT makes the remaining transitions fast. This combination is common in advanced DP.