3929. Minimum Partition Score II

Use prefix sums to rewrite the value of any subarray in O(1).

Consider DP transitions of the form: dp[i] = min(dp[j] + cost(j + 1, i)). Expand the cost formula algebraically. The transition can be rewritten as a minimum over linear functions.

Instead of DP on the number of partitions, add a penalty for creating a subarray and binary search that penalty.