Cod sursa(job #2306392)

Utilizator UnseenMarksmanDavid Catalin UnseenMarksman Data 22 decembrie 2018 11:30:53
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <climits>
#define maxn 200000
using namespace std;

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

long long n, v[2*maxn+2];
long long dq[2*maxn+2], fr, bk, s=LLONG_MIN, posi, posj;

int main()
{
    int semn;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i]>>semn;
        if(semn)
        {
            v[i+n]=v[i];
        }
        else
        {
            v[i+n]=v[i]=-v[i];
        }
    }
    fr=1;bk=0;
    for(int i=1; i<=2*n; i++)
    {
        v[i]+=v[i-1];
        if(s<v[i]-v[dq[fr]])
        {
            s=v[i]-v[dq[fr]];
            posi=i;
            posj=dq[fr]+1;
        }
        while(fr<=bk&&v[i]<=v[dq[bk]]) bk--;

        dq[++bk]=i;
        if(i-dq[fr]==n) fr++;
    }
    fout<<s<<' '<<posj<<' '<<(posi-posj+1);
    return 0;
}