题解满了。

过了以后发现题解都是 $O(nk\log n)$ 的高妙模拟费用流做法。

我的做法是暴力维护 dp，类似于最大子段和合并。复杂度 $O(nk^2\log n)$，但是常数应该小于正解。而且 CF 时限没有卡的很紧。