Submission #5906818

---

Source Code Expand

#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vll; template<class T>using vv = vector<vector<T>>;
template<class T>vv<T> vvec(size_t n, size_t m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int main() {
    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    vll sumA(N + 1);
    rep(i, N) sumA[i + 1] = sumA[i] + A[i];
    
    ll sumq[4];
    sumq[0] = A[0], sumq[1] = A[1];
    sumq[2] = A[2], sumq[3] = sumA[N] - sumA[3];
    int q1 = 1;
    int q3 = 3;
    for (; q3 < N - 1; ) {
        if (abs(sumq[2] - sumq[3] + 2 * A[q3]) < abs(sumq[2] - sumq[3])) {
            sumq[2] += A[q3];
            sumq[3] -= A[q3];
            q3++;
        }
        else break;
    }

    ll ans = *max_element(sumq, sumq + 4) - *min_element(sumq, sumq + 4);
    for (int half = 2; half < N - 2; ) {
        sumq[1] += A[half];
        sumq[2] -= A[half];
        half++;
        for (; q1 < half - 1; ) {
            if (abs(sumq[0] - sumq[1] + 2 * A[q1]) < abs(sumq[0] - sumq[1])) {
                sumq[0] += A[q1];
                sumq[1] -= A[q1];
                q1++;
            }
            else break;
        }

        for (; q3 < N - 1; ) {
            if (abs(sumq[2] - sumq[3] + 2 * A[q3]) < abs(sumq[2] - sumq[3])) {
                sumq[2] += A[q3];
                sumq[3] -= A[q3];
                q3++;
            }
            else break;
        }

        ans = min(ans, *max_element(sumq, sumq + 4) - *min_element(sumq, sumq + 4));
    }

    write(ans);
}

Submission Info

Judge Result