CF1442D Sum

题意：给定 个不降的数组。

进行如下操作 次：

将 加上某个数组的第一个元素，并将其删除。

最大化操作完成后 的值。

数组元素总个数 ，，时限 。

---

视为背包问题：将一个数组 看做一个泛化物品，提供 的容量可以得到的价值为 。

由于 不降，价值 上凸。

若存在两个数组 ，容量上界分别为 ，且目前提供的容量分别为 。

若 ，则将 一个减一，另一个加一。

收益的变化量为 或 。

由于序列不降的性质，有 。

若两种情况的收益都 则 ，矛盾。

故一定有一种调整不会使得局面变差。

因此，若同时存在两个数组“取了一部分”，则不是最优解。存在最优解使得至多只有一个数组取了一部分。

---

枚举取一部分的数组，求出其他所有数组的背包，然后枚举自己取的个数。

“每个物品消失后的背包”是经典问题，容易使用线段树分治在 内完成。

最后的枚举量是 的。