Cod sursa(job #2414784)

Utilizator qThunderStefan Durlanescu qThunder Data 25 aprilie 2019 00:59:20
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,k,que[400004],v[400004],p,u,p1,l,a;
long long maxim;
int main()
{
    fin>>n;
    int stare;
    for(int i=1;i<=n;i++)
    {
        fin>>a>>stare;
        if(stare==0)
            a*=-1;
        v[i]=v[i-1]+a;
        v[i+n]=a;
    }
    for(int i=n+1;i<=2*n;i++)
        v[i]+=v[i-1];
    que[1]=0;
    u=p=1;
    for(int i=1;i<=2*n;i++)
    {
        while(p<=u && v[i]<v[que[u]])
            u--;
        que[++u]=i;
        if(que[u]-que[p]==n+1)
        {
            p++;
        }
        if(v[que[u]]-v[que[p]]>maxim)
        {
            maxim=v[que[u]]-v[que[p]];
            p1=que[p]+1;
            l=que[u]-que[p];
        }
    }
    fout<<maxim<<" "<<p1<<" "<<l;
    return 0;
}