下次记得交题前再测一遍样例。

· · 题解

纪念一下这道赛时因忘删调试而爆零的题。

首先这是一个两只 \log 的做法，各方面均劣于 std 做法（

考虑朴素 dp 怎么做：记 s 为 a 的前缀和，f_i 表示划分到 i 时的答案。
有转移：

f_i\gets\max_{j\lt i}\{\min(f_j, s_i-s_j+b_{j+1}+c_i)\}

这样直接做是 O(n^2) 的。

考虑优化。先把上面的式子改写一下：

f_i\gets s_i+c_i+\max_{j\lt i}\{\min(f_j-s_i-c_i, b_{j+1}-s_j)\}

考虑二分后面那个 \max 的取值，那我们只需要 check 是否存在 j\lt i，使得 b_{j+1}-s_j\ge mid, f_j\ge mid+s_i+c_i。

进一步地，将 check 转化为判断 \max\limits_{b_{j+1}-s_j\ge mid}f_j 是否大于等于 mid+s_i+c_i，这个可以拿树状数组维护。

时间复杂度 O(n\log n\log V)。

code.