CF846C

// Problem: C. Four Segments
// Contest: Codeforces - Educational Codeforces Round 28
// URL: https://codeforces.com/contest/846/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifdef __DEBUG__
#include "dbg.h"
#else
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char **argv)
{
    int n;
    cin >> n;
    vi arr(n);
    for (auto &x : arr)
        cin >> x;
    vl acc(n + 1);
    for (int i = 0; i < n; ++i)
        acc[i + 1] = acc[i] + arr[i];
    int a = 0, b = 0, c = 0;

    using a2l = array<ll, 2>;
    vector<a2l> prev(n + 1);

    for (int i = 1; i <= n; ++i) {
        if (acc[i] > prev[i - 1][0])
            prev[i] = a2l{acc[i], i};
        else
            prev[i] = prev[i - 1];
        // dbg(prev[i][0], prev[i][1]);
    }
    ll maxv = 0;
    ll val = 0;
    using a3l = array<ll, 3>;
    vector<a3l> post(n + 1);
    post[n] = {0, n, n};
    int op1 = n, op2 = n;
    for (int i = n, j = n; i > 0; --i) {
        val += arr[i - 1];
        if (val >= maxv)
            maxv = val, op1 = i - 1, op2 = j;
        if (val <= 0)
            j = i - 1, val = 0;
        post[i - 1] = {maxv, op1, op2};
    }
    maxv = -1e18;
    for (int i = 0; i <= n; ++i) {
        val = prev[i][0] + post[i][0];
        if (val > maxv)
            dbg(i, prev[i][0], post[i][0]), dbg(post[i][0], post[i][1], post[i][2]), a = prev[i][1], b = post[i][1],
                                                                                     c = post[i][2], maxv = val;
    }
    dbg(2 * maxv - acc[n]);
    dbg(acc[a], acc[b], acc[c], acc[n]);
    cout << a << ' ' << b << ' ' << c << endl;
    return 0;
};

int main1(int argc, char **argv)
{
    int n;
    cin >> n;
    vi arr(n);
    for (auto &x : arr)
        cin >> x;
    vl acc(n + 1);
    for (int i = 0; i < n; ++i)
        acc[i + 1] = acc[i] + arr[i];
    int a = 0, b = 0, c = 0;

    using a2l = array<ll, 2>;
    vector<a2l> prev(n + 1);

    for (int i = 1; i <= n; ++i) {
        if (acc[i] > prev[i - 1][0])
            prev[i] = a2l{acc[i], i};
        else
            prev[i] = prev[i - 1];
        dbg(prev[i][0], prev[i][1]);
    }
    ll maxv = -1e18;
    ll val = 0;
    dbg(val, prev[n][1], n);
    ll suf = acc[n], k = n;
    for (int i = n; i >= 0; --i) {
        if (acc[i] > suf)
            suf = acc[i], k = i;
        ll t = prev[i][0] - acc[i] + suf;
        if (t > maxv)
            maxv = t, a = prev[i][1], b = i, c = k;
    }

    cout << a << ' ' << b << ' ' << c << endl;
    return 0;
};