Cut the sequence into three [WASEDAJITSUGYO_SCIENCECLUB_FESTIVAL_CONTEST2019 E]

https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/cut-the-sequence-into-three

解説

https://www.hackerrank.com/contests/wasedajitsugyo-scienceclub-festival-contest2019/challenges/cut-the-sequence-into-three/submissions/code/1316764450

嘘解法かもしれない。
難しい問題に見える。
取り組み方がパッと思いつかないので、とりあえず全探索。
stの選ぶ場所を全探索すると、累積和を使ってO(N²)が達成できる。
sを固定にするとtは下に凸の関数になってたりしないかなー。
Full Feedbackだし、出して通れば嬉しいなーと思うと通る。

template<typename Func>
int findMin(int L, int R, Func f) { //[L, R)
    int lo = L - 1, hi = R - 1;
    while (lo + 1 != hi) {
        int mi = (lo + hi) / 2;
        if (f(mi) <= f(mi + 1)) hi = mi;
        else lo = mi;
    }
    return hi;
}











int N, A[101010];
//---------------------------------------------------------------------------------------------------
ll sm[101010];
void pre() {
    sm[0] = A[0];
    rep(i, 1, N) sm[i] = sm[i - 1] + A[i];
}
ll get(int L, int R) { // [L, R]
    if (L > R) return 0;
    ll res = sm[R];
    if(0 < L) res -= sm[L - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
int ss;
ll f(int s, int t) {
    ll ma = -1;
    chmax(ma, get(0, s));
    chmax(ma, get(s + 1, t));
    chmax(ma, get(t + 1, N - 1));

    ll mi = infl;
    chmin(mi, get(0, s));
    chmin(mi, get(s + 1, t));
    chmin(mi, get(t + 1, N - 1));

    return ma - mi;
}
//---------------------------------------------------------------------------------------------------
void _main()
{
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    pre();

    ll ans = infl;
    rep(s, 0, N) {
        ss = s;
        int opt_t = findMin(s, N, [](int t) {
            return f(ss, t);
        });
        chmin(ans, f(s, opt_t));
    }
    cout << ans << endl;
}