Codeforces 321E Ciel and Gondola - Implementation

Here's the D&C solution:

function solve(g, l, r, optL, optR, dp, cost)
    if l > r then
        return
    mid := (l + r) / 2
    opt := optL
    dp[g][mid] := infinity
    for j from optL to min(optR, mid - 1)
        val := dp[g-1][j] + cost[j+1][mid]
        if val < dp[g][mid] then
            dp[g][mid] := val
            opt := j
    solve(g, l, mid-1, optL, opt, dp, cost)
    solve(g, mid+1, r, opt, optR, dp, cost)
    // Each layer g: solve(g, 1, n, 0, n-1, dp, cost)

Time: $O(k \cdot n \log n)$. Precompute $cost$ in $O(n^2)$. The QI property guarantees that optimal splits are monotonic, enabling the Knuth improvement.

Space: $O(n \cdot k)$ for the DP table.

Time: $O(n \cdot k \log n)$. Space: $O(n \cdot k)$.