Submission #2771453

---

Source Code Expand

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back

using namespace std;
typedef long long int ll;

ll find(ll pref[], int lim, ll val){
	ll l = 0, r = lim;
	while (l < r){
		ll m = (l+r+1)/2;
		if (2*pref[m] <= val) l = m;
		else r = m-1;
	}
	if (l < lim-1){
		ll k = l+1;
		if (abs(2*pref[k]-val) < abs(2*pref[l]-val)) return pref[k];
	}
	return pref[l];
}

ll find2(ll pref[], int lim, ll val, int n){
	ll l = lim+1, r = n-1;
	while(l < r){
		ll m = (l+r+1)/2;
		if (2*(pref[m]-pref[lim]) <= val) l = m;
		else r = m-1;
	}
	if (l < n-2){
		ll k = l+1;
		if (abs(2*(pref[k]-pref[lim])-val) < abs(2*(pref[l]-pref[lim])-val)) return pref[k]-pref[lim];
	}
	return pref[l]-pref[lim];
}

int main(void){
	// #ifndef JUDGE
	// freopen("in.txt", "r", stdin); 
	// #endif
	fast;
	int n; cin >> n;
	ll a[n], pref[n];
	for (int i = 0; i < n; ++i){
		cin >> a[i];
		if (i) pref[i] = a[i] + pref[i-1];
		else pref[i] = a[i];
	}
	ll ans = 1e18;
	for (int i = 1; i < n-2; ++i){
		ll left = pref[i];
		ll one = find(pref, i, left);
		ll two = pref[i] - one;
		ll three = find2(pref, i, pref[n-1]-pref[i], n);
		ll four = pref[n-1]-pref[i]-three;
		ll cur = max({one, two, three, four}) - min({one, two, three, four});
		ans = min(cur, ans);
	}
	cout << ans << '\n';

}

Submission Info

Judge Result