Server Allocation - Implementation

Precompute prefix sums $S[i] = \sum_{t=0}^{i-1} w_t$. Cost of $[l, r] = (S[r+1] - S[l])^2$. D&C recursion: for layer $j$, compute all $dp[j][i]$ using the monotonicity of optimal splits. Base: $dp[1][i] = (S[i])^2$ (all tasks on one server). Fill layers 2 to $k$. Final answer: $dp[k][n]$. Time: $O(kn \log n)$. Space: $O(n)$ if we only keep two layers. Keep only two layers in memory since each layer only depends on the previous. This saves space.

Time complexity: $O(kn \log n)$.

Space complexity: $O(n)$ using two-layer rolling array.