提出 #2769443

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;

const ll MOD = 1000 * 1000 * 1000 + 7;
const ll INF = (ll)1e18;

struct PrefixSum {
    vector<ll> p;

    PrefixSum(const vector<ll>& a): p(a.begin(), a.end()) {
        for (size_t i = 1; i < p.size(); ++i)
            p[i] += p[i - 1];
    }

    ll get(int l, int r) const {
        assert(l <= r);
        assert(l >= 0);
        assert(r < p.size());
        ll ans = p[r];
        if (l > 0)
            ans -= p[l - 1];
        return ans;
    }
};

ll get_ans(ll a, ll b, ll c, ll d) {
    ll mx = max(max(a, b), max(c, d));
    ll mn = min(min(a, b), min(c, d));
    if (mn == 0)
        return INF;
    return mx - mn;
}

int get_pos(const PrefixSum& ps, int lo, int hi) {
    assert(hi - lo >= 1);
    int l = lo;
    int r = hi;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (ps.get(lo, m) < ps.get(m + 1, hi))
            l = m;
        else
            r = m;
    }
    return l;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) {
        cin >> x;
    }
    ll ans = INF;
    PrefixSum ps(a);
    for (int i = 2; i + 2 <= n; i++) {
         int p1 = get_pos(ps, 0, i - 1);
         int p2 = get_pos(ps, i, n - 1);
         for (int d1 = -5; d1 <= 5; d1++)
             for (int d2 = -5; d2 <= 5; d2++) {
                int l = p1 + d1;
                int m = i;
                int r = p2 + d2;
                if (l <= 0)
                    continue;
                if (r >= n)
                    continue;
                if (m <= l)
                    continue;
                if (r <= m)
                    continue;
                ans = min(ans, get_ans(ps.get(0, l - 1), ps.get(l, m - 1), ps.get(m, r - 1), ps.get(r, n - 1)));
             }
    }
    cout << ans << endl;
}

提出情報

ジャッジ結果