CF846C WA

// 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};
    for (int i = n, j = n; i > 0; --i) {
        val += arr[i - 1];
        if (val < 0)
            j = i, val = 0;
        if (val > maxv) {
            maxv = val;
            post[i - 1] = {val, i - 1, j};
        } else {
            post[i - 1] = post[i];
        }
    }
    maxv = -1e18;
    for (int i = 1; i <= n; ++i) {
        val = prev[i - 1][0] + post[i][0];
        dbg(prev[i - 1][0], post[i][0]);
        if (val > maxv)
            a = prev[i - 1][1], b = post[i][1], c = post[i][2], maxv = val;
    }

    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;
    }

    /*
    for (int i = prev[n][1], j = n, k = n; j > 0;) {
        while (j > i && val > 0) {
            val = val + arr[j - 1];
            if (val + prev[i][0] > maxv) {
                maxv = val + prev[i][0];
                a = i, b = j, c = k;
            }
            dbg(i, j, k, val);
            j--;
        }
        if (val < 0) {
            k = j;
            val = 0;
        }
        --j;
        i = prev[i - 1][1];
    }
    */
    cout << a << ' ' << b << ' ' << c << endl;
    return 0;
};