差分约束算法：给出 \(m\) 个不等式形如 \(x_{a_i} \le x_{b_i} + y_i\)，求是否有解。
考虑把不等式看成图上的三角不等式 \(dis_v \le dis_u + d\)，连边 \((b_i, a_i, y_i)\)，以 \(x_i\) 最大的位置跑最短路，如果图中有负环就无解。此时求出来的 \(dis_i\) 是 \(x_i \le 0\) 的最大解。
考虑二分答案 \(x\)，记 \(s\) 为前缀和数组，那么我们可以得到不等式：
- \(s_0 = 0, s_{2n} = x\)，连边 \((0, 2n, x), (2n, 0, -x)\)；
- \(s_i - s_{i-1} \ge 0\)，连边 \((i, i - 1, 0)\)；
- \(i \in [0,n), s_{i+n} - s_i \ge a_i\)，连边 \((i + n, i, -a_i)\)；
- \(i \in [0,n), x - (s_{i+n} - s_i) \ge a_{i+n}\)，连边 \((i, i + n, x - a_{i+n})\)。
直接跑 spfa 会 T。注意到删去 \(n\) 点后图长这样：
可以 dp 求出 \(2n\) 到 \(n-1, n+1, 0\) 的最短路，以及 \(n-1\) 到 \(0, n+1\) 的最短路。加上新点 \(n\) 后，只用计算与新加边有关的点，把整张图缩成 \(0, n-1, n, n+1, 2n\) 五个点，在新图上跑 spfa 即可。
总结：这种差分约束但是又不能直接跑 spfa 的题，考虑观察图的形态，用 dp 求出最短路，或者缩点。
code
// Problem: F - Gateau
// Contest: AtCoder - AtCoder Regular Contest 117
// URL: https://atcoder.jp/contests/arc117/tasks/arc117_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 300100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, a[maxn], m, f[maxn], head[maxn], len, g[maxn];
bool vis[maxn];
struct edge {
ll to, dis, next;
} edges[99];
inline void add_edge(ll u, ll v, ll d) {
edges[++len].to = v;
edges[len].dis = d;
edges[len].next = head[u];
head[u] = len;
}
inline bool spfa() {
queue<int> q;
mems(f, 0x3f);
mems(vis, 0);
mems(g, 0);
f[m] = 0;
g[m] = 1;
vis[m] = 1;
q.push(m);
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = edges[i].next) {
ll v = edges[i].to, d = edges[i].dis;
if (f[v] > f[u] + d) {
f[v] = f[u] + d;
if (!vis[v]) {
vis[v] = 1;
if ((++g[v]) >= 8) {
return 0;
}
q.push(v);
}
}
}
}
return 1;
}
inline bool check(ll x) {
len = 0;
mems(head, 0);
mems(f, 0);
f[m - 1] = f[m] = 0;
f[n - 1] = -a[n - 1];
for (int i = n - 2; i; --i) {
f[i] = f[i + 1];
f[i + n] = f[i + n + 1];
ll p = f[i], q = f[i + n];
f[i] = min(f[i], q - a[i]);
f[i + n] = min(f[i + n], p + x - a[i + n]);
}
f[0] = f[1];
add_edge(m, 0, f[0]);
add_edge(m, n + 1, f[n + 1]);
add_edge(m, n - 1, f[n - 1]);
mems(f, 0);
f[n - 1] = 0;
f[m - 1] = x - a[m - 1];
for (int i = n - 2; i; --i) {
f[i] = f[i + 1];
f[i + n] = f[i + n + 1];
ll p = f[i], q = f[i + n];
f[i] = min(f[i], q - a[i]);
f[i + n] = min(f[i + n], p + x - a[i + n]);
}
f[0] = f[1];
add_edge(n - 1, n + 1, f[n + 1]);
add_edge(n - 1, 0, f[0]);
add_edge(n, n - 1, 0);
add_edge(n + 1, n, 0);
add_edge(n, 0, -a[0]);
add_edge(m, n, -a[n]);
add_edge(0, m, x);
add_edge(m, 0, -x);
return spfa();
}
void solve() {
scanf("%lld", &n);
m = (n << 1);
ll l = 0, r = 1e10, ans = -1;
for (int i = 0; i < m; ++i) {
scanf("%lld", &a[i]);
}
if (n == 1) {
printf("%lld\n", a[0] + a[1]);
return;
}
for (int i = 0; i < n; ++i) {
l = max(l, a[i] + a[i + n]);
}
while (l <= r) {
ll mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}