Submission #2873197

---

Source Code Expand

#pragma GCC optimize("O3")
#define first x
#define second y
#include <bits/stdc++.h>

using namespace std;

enum {MOD0 = 1000000000, MOD7 = 1000000007, MOD9 = 1000000009};
typedef unsigned short ushort;typedef unsigned int uint;typedef long long ll;typedef unsigned long long ull;
#ifndef CrafterKolyan
#define endl '\n'
#endif

int a[200000];
ll sum[200001];

signed main() {
#ifndef CrafterKolyan
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum[i + 1] = sum[i] + a[i];
    }
    ll l = 1, r = 3;
    ll ans = LLONG_MAX;
    for (ll m = 2; m < n; ++m) {
        r = max(r, m + 1);

        while (l + 1 < m && abs(sum[m] - 2 * sum[l]) >= abs(sum[m] - 2 * sum[l + 1])) ++l;
        while (r + 1 < n && abs(sum[n] - 2 * sum[r] + sum[m]) >= abs(sum[n] - 2 * sum[r + 1] + sum[m])) ++r;
        ll a[4] = {
            sum[l],
            sum[m] - sum[l],
            sum[r] - sum[m],
            sum[n] - sum[r]
        };
        sort(a, a + 4);
        ans = min(ans, a[3] - a[0]);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result