Codeforces 321E Ciel and Gondola - Walkthrough

Partition $n$ people into $k$ groups to reduce total cost. Cost of group $[l, r]$ depends on prefix sums. $dp[j][i]$ = min cost to partition first $i$ people into $j$ groups.

Transition: try all splits. QI holds for the cost function. Apply D&C: for layer $j$, compute all $dp[j][i]$ in $O(n \log n)$ using the recursion. Total: $O(kn \log n)$ instead of $O(kn^2)$. For $k = 100$, $n = 10^5$, this is the difference between TLE and AC.