Submission #2773739

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 0
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;
#define MAX_N 200010

template< typename T >
class CumulativeSum
{
public:
    vector< T > m_data;
    CumulativeSum() {};
    CumulativeSum(int sz) : m_data(sz, 0) {};

    // k に x を加える O(1)
    void Add(int k, int x) {
        assert(m_data.size() >= k);
        if(m_data.size() <= k) { m_data.push_back(x); }
        else { m_data[k] += x; }
    }

    // 累積和の構築 O(m_data.size())
    void Build() { for(int i = 1; i < m_data.size(); i++) { m_data[i] += m_data[i - 1]; } }

    // 区間 [0, k] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int k) {
        if(k < 0) { return 0; }
        return (m_data[min(k, (int) m_data.size() - 1)]);
    }

    // 区間 [l, h] の和を返す O(1)
    // 閉区間なので k が含まれることに注意
    T Query(int l, int h) { return this->Query(h) - this->Query(l-1); }
};


ll N;
ll A[MAX_N] = {};

signed main()
{
    CumulativeSum<ll> cs;

    cin >> N;
    REP(i, N) {
        cin >> A[i];
        cs.Add(i, A[i]);
    }
    cs.Build();

    // だいたい 3 倍くらいになる場所を求める
    pair<int ,int> cand1 = {0, LLINF};
    for(int i = 0; i < N-4; ++i) {
        ll left = cs.Query(0, i);
        ll right = cs.Query(i+1, N-1);
        ll sub = abs(left * 3 - right);
        if(cand1.second > sub) { cand1= {i, sub}; }
    }

    pair<int ,int> cand2 = {0, LLINF};
    for(int i = 0; i < N-2; ++i) {
        ll left = cs.Query(0, i);
        ll right = cs.Query(i+1, N-1);
        ll sub = abs(left - right);
        if(cand2.second > sub) { cand2= {i, sub}; }
    }

    pair<int ,int> cand3 = {0, LLINF};
    for(int i = 3; i < N-1; ++i) {
        ll left = cs.Query(0, i);
        ll right = cs.Query(i, N-1);
        ll sub = abs(left - right * 3);
        if(cand3.second > sub) { cand3= {i, sub}; }
    }

    ll ans = LLINF;
    for(int i = -100; i <= 100; ++i) {
        ll border1 = cand1.first + i;
        if(border1 < 0 || border1 > N - 4) { continue; }
        for(int j = -100; j <= 100; ++j) {
            ll border2 = cand2.first + j;
            if(border2 <= border1 || border2 > N - 3) { continue; }
            for(int k = -100; k <= 100; ++k) {
                ll border3 = cand3.first + k;
                if(border3 <= border2 || border3 > N - 2) { continue; }
                ll max_a = 0;
                ll min_a = LLINF;
                DBG("[%lld, %lld]: %lld\n", 0, border1, cs.Query(0, border1));
                DBG("[%lld, %lld]: %lld\n", border1+1, border2, cs.Query(border1+1, border2));
                DBG("[%lld, %lld]: %lld\n", border2+1, border3, cs.Query(border2+1, border3));
                DBG("[%lld, %lld]: %lld\n", border3+1, N-1, cs.Query(border3+1, N-1));
                max_a = max(max_a, cs.Query(0, border1));
                max_a = max(max_a, cs.Query(border1 + 1, border2));
                max_a = max(max_a, cs.Query(border2 + 1, border3));
                max_a = max(max_a, cs.Query(border3 + 1, N - 1));
                min_a = min(min_a, cs.Query(0, border1));
                min_a = min(min_a, cs.Query(border1 + 1, border2));
                min_a = min(min_a, cs.Query(border2 + 1, border3));
                min_a = min(min_a, cs.Query(border3 + 1, N - 1));
                ans = min(ans, abs(max_a - min_a));
                DBG("ans: %lld cand: %lld\n", ans, abs(max_a - min_a));
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Submission Info

Judge Result