解法
4 つの区間に分けるので，仕切りは 3つで，それを \(i,j,k\ (i < j < k)\) とする． 3つの仕切りのうち，真ん中 \(j\) にあるものを固定すると，残りの 2つが対称になりそうで楽そう． \(j\) を固定したときのベストな \(i,k\) を \(i_{j}, k_{j}\) とおく．
\(j\) により左右 2つに分解したとき，\(i\) の位置は
- \(P = sum_{[0,i)} A \)と\(Q = sum_{[i,j)} A\) が同じくらいになるとよい．
- \(A\) の元はすべて \(0\)以上なので，\(i_{j}\) は単調増加．
後者から，\(i_{j}\) は尺取り法で求められる． 前者に注意しながら尺取り法を実装する． \(P\) と \(Q\) が同じ位になるには，\(P\) と \(Q\) の大小関係が入れ替わる高々 2つが \(i_{j}\) の候補となる．
\(k_{j}\) についても同様． 各 \(j\) に対して，\(i_{j}\) と \(k_{j}\) が高々 2通りずつあるで，高々 2x2通り試せば良い．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
vll sum(n+1); rep(i,n) sum[i+1] = sum[i] + a[i];
// a,b,i: partitions of n
// i in [a,b]
vector<pll> ret;
while(i <= b && sum[i] - sum[a] < sum[b] - sum[i]){
i++;
}
i--;
srep(j,i,i+2){
if(in(j, a+1, b)) {
ll ma = max(sum[j]-sum[a], sum[b] - sum[j]);
ll mi = min(sum[j]-sum[a], sum[b] - sum[j]);
ret.emplace_back(ma, mi);
}
}
return ret;
};
const ll inf = 2e14 + 100;
ll ans = inf;
ll l = 0, r = 0;
rep(i,n+1){
chmax(r,i); chmin(r,n);
chmin(l,i); chmax(l,0LL);
for(auto [ma_l, mi_l]: f(0,i,l)){
for(auto [ma_r, mi_r]: f(i,n,r)){
ll ma = max(ma_l, ma_r);
ll mi = min(mi_l, mi_r);
chmin(ans, ma - mi);
}
}
}
cout << ans << endl;
return 0;
}
