AtCoder Beginner Contest 102D

D - Equal Cut

4つに分割する，つまり境目は3か所．

3つの場合は，真ん中を全探索して残りを高速に求めるケースが多く，今回もそれ．

分割する場所を左から l, i, r とおいて，i を全探索．

2分探索で，残りの2か所を求める．

・なるべく均等に分割するのが最善

・l, r は独立

累積和を求めておけば，分割したときのそれぞれの和がO(1)で求まる．

分割したときの左の和をb, 右の和をc とおいて，2分探索で b <= c となる境目 it を求める．

it または it+1 のどちらかが最善．

これで l が求まるので，同様に r も求める．

typedef long long ll;

const ll INFL = 1LL << 60;

using vll = vector<long long>;  using vvll = vector<vll>;

using pll = pair<ll,ll>;

int main() {

    ll n;

    cin >> n;

    vll a(n); rep(i,n) { cin >> a[i]; }

    vll s(n+1); rep(i,n) s[i+1] = s[i] + a[i];

    ll ans = INFL;

    rep(i,n+1){

        auto f = [&](ll l, ll r, vll* v) -> void { // v: 答えの候補を入れる

            ll ok, ng;

            ok = l-1, ng = r;

            while(abs(ok-ng) > 1){

                ll md = (ok + ng)/2;

                ll b,c;

                b = s[md] - s[l];

                c = s[r] - s[md];

                if(b <= c) ok = md;

                else ng = md;

            }

            v->push_back(ok);

            v->push_back(ok+1);

        };

       

        vll L,R;

        f(0,i,&L);

        f(i,n,&R);

        fore(l,L) fore(r,R){

            ll ma = -INFL, mi = INFL;

            chmax(ma, s[l]-s[0]);

            chmax(ma, s[i]-s[l]);

            chmax(ma, s[r]-s[i]);

            chmax(ma, s[n]-s[r]);

            chmin(mi, s[l]-s[0]);

            chmin(mi, s[i]-s[l]);

            chmin(mi, s[r]-s[i]);

            chmin(mi, s[n]-s[r]);

            chmin(ans, abs(ma-mi));

        }

    }

    cout << ans << endl;

    return 0;

}