$O(n^2)$ 和二分答案 $O(n\log V)$ 的做法不在这里讲，这里我们只讲利用前缀/后缀 $\min$ 性质的 $O(n)$ 做法。

我们设 $s_i$ 为“以 $0$ 号城市为起点”作为前提，从 $i$ 号城市能够成功出发，巡查所带来的能量总增量（可能为负）。则有：

• $s_0=-a_0$
• $s_i=s_{i-1}+(b_i-a_i)$

这个不解释，从 $i$ 出发会先获得 $b_i$ 的补给，再消耗 $a_i$ 的能量。

我们可以对 $s_i$ 分别做一次前缀 $\min$ 后缀 $\min$，对于以每一个城市为起点的计算，显然其过程中的最小能量总增量决定了答案，最小值的相反数即为答案。

从 $i$ 成功出发到 $n$ 成功出发的这一段，利用后缀 $\min$就可以求了，需要注意的是，此时不存在 $b_i$ 的补给，这段后缀 $\min$ 减去 $b_i$ 即可；而从 $0$ 号城市出发到 $i-1$ 号城市出发这一段，正常使用前缀 $\min$ 去求即可。

一个边界情况为：当全程的最小能量总增量均 $\ge 0$ 时，此时答案是 $0$。

#include <stdio.h>
#include <algorithm>
inline int rd()
{
    int k = 0, f = 1;
    char s = getchar();
    while (s < '0' || s > '9') f = (s == '-') ? 0 : f, s = getchar();
    while (s >= '0' && s <= '9') k = (k << 1) + (k << 3) + (s ^ '0'), s = getchar();
    return f ? k : -k;
}
inline void wr(int x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int N = 100010;
int n;
int a[N], b[N];

int pre_s[N], suf_s[N];
int pre_mn[N], suf_mn[N];

int main()
{
    n = rd();
    for (int i = 0; i <= n; ++i) a[i] = rd();
    for (int i = 1; i <= n; ++i) b[i] = rd();

    pre_s[0] = pre_mn[0] = -a[0];
    for (int i = 1; i <= n; ++i) pre_s[i] = pre_s[i - 1] + (b[i] - a[i]), pre_mn[i] = std::min(pre_mn[i - 1], pre_s[i]);
    suf_mn[n] = pre_s[n];
    for (int i = n - 1; i >= 0; --i) suf_mn[i] = std::min(suf_mn[i + 1], pre_s[i]);

    for (int i = 1; i <= n; ++i, putchar(' '))
        wr(-std::min(std::min(pre_mn[i - 1], suf_mn[i] - b[i]), 0));
}