Cod sursa(job #2811370)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 2 decembrie 2021 00:04:43
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

int a[200001], ss[200001];
int N, semn, poz = 1, sum, amx = INT_MIN, aamx = INT_MIN, apoz, len;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("buline");

    cin >> N;
    for(int i = 1;i <= N;i++) {
        cin >> a[i] >> semn;
        if(semn == 0) a[i] = -a[i];
    }

    for(int i = 1;i <= N;i++) {
        ss[i] = ss[i - 1] + a[i];
        sum += a[i];

        if(sum > amx) {
            amx = sum;
            apoz = poz;
            len = i - poz + 1;
        }

        if(sum < 0) {
            sum = 0;
            poz = i + 1;
        }
    }

    for(int i = 1;i < N;i++) {
        if(ss[i] > aamx)
            aamx = ss[i], poz = i;

        if(aamx + ss[N] - ss[i] > amx) {
            amx = aamx + ss[N] - ss[i];
            len = poz + (N - i);
            apoz = i + 1;
        }
    }

    cout << amx << " " << apoz << " " << len;

    return 0;
}