Cod sursa(job #2811739)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 2 decembrie 2021 23:59:05
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 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
}

deque <int> dq;

int sum[400001];
int N, op, ans, poz, len;

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

    Open("buline");

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

    dq.push_back(1), ans = sum[1], poz = 1, len = 1;
    for(int i = 2;i <= 2 * N;i++) {
        sum[i] += sum[i - 1];

        while(!dq.empty() && i - dq.front() > N) {
            dq.pop_front();
        }

        if(sum[i] - sum[dq.front()] > ans) {
            ans = sum[i] - sum[dq.front()];
            len = i - dq.front();
            poz = dq.front() + 1;
        }

        while(!dq.empty() && sum[dq.back()] > sum[i]) {
            dq.pop_back();
        }

        dq.push_back(i);
    }

    cout << ans << " " << poz << " " << len;


    return 0;
}