Server Allocation - Problem Statement

Allocate $n$ tasks to $k$ servers. Server cost = sum of (task weights)^2 for assigned tasks. Find the lowest total. $dp[j][i]$ = min cost to assign first $i$ tasks to $j$ servers.

Transition: split at some point for the $j$-th server. Cost of assigning $[l, r]$ to one server = $(\sum_{t=l}^{r} w_t)^2$. Use prefix sums. QI holds for this squared-sum cost. Apply D&C: $O(kn \log n)$. The squared sum cost encourages even distribution. Putting all tasks on one server gives high cost.