Cod sursa(job #2588262)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 24 martie 2020 16:35:48
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>

#define NMAX 200005
using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

long long v[2 * NMAX], s[2 * NMAX], dq[2 * NMAX], in = 1, sf = 1;

int main()
{
    int n;
    fin >> n;

    for(int i = 1; i <= n; ++i){
        int tip;
        fin >> v[i] >> tip;

        v[i] *= (tip == 0 ? -1 : 1);
        s[i] = s[i - 1] + v[i];
    }
    for(int i = n + 1; i <= 2 * n; ++i){
        v[i] = v[i - n];
        s[i] = s[i - 1] + v[i];
    }

    dq[in] = 0;
    int maxx = -10005, stF, lgF;
    for(int i = 1; i <= 2 * n; ++i){
        while(in <= sf && s[i] <= s[dq[sf]])
            --sf;
        dq[++sf] = i;
        if(i - dq[in] - 1 == n)
            ++in;
        if(s[i] - s[dq[in]] > maxx){
            maxx = s[i] - s[dq[in]];
            stF = dq[in] + 1;
            lgF = i - dq[in];
        }
    }
    fout << maxx << ' ' << stF << ' ' << lgF << '\n';
    return 0;
}