Cod sursa(job #2414494)

Utilizator BogauuuBogdan Ivancu Bogauuu Data 24 aprilie 2019 17:07:51
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>

using namespace std;

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

bool p;
int n,i,x,st,dr,curent,maxim,s,l,a[400010],d[400010];

int main()
{
    fin >> n;
    for (i=1;i<=n;i++)
    {
        fin >> x >> p;
        if (p==0) x*=-1;
        a[i]=a[i-1]+x;
        a[n+i]=a[n+i-1]+x;
    }
    for (i=n+1;i<=2*n;i++) a[i]+=a[n];
    st=1;
    dr=1;
    d[dr]=0;
    for (i=1;i<=n*2;i++)
    {
        while (st<=dr && a[i]<a[d[dr]]) dr--;
        dr++;
        d[dr]=i;
        if (i-d[st]==n+1) st++;
        curent=a[i]-a[d[st]];
        if (curent>maxim)
        {
            s=d[st];
            l=i-s;
            maxim=curent;
        }
    }
    if (s==n) s=0;
    fout << maxim << " " << s+1 << " " << l;

    return 0;
}