Cod sursa(job #2636873)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 20 iulie 2020 15:03:39
Problema Buline Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>

using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
long long n,x,y,Max,s,k,p,u,a[50001],b[50001];
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>x>>y;
        if(y==0)x=-x;
        a[i]=a[i-1]+x;
        a[i+n]=x;
    }
    for(int i=n+1; i<=2*n; i++)
    {
        a[i]=a[i]+a[i-1];
    }
    p=1;
    b[++u]=0;
    for(int i=1; i<=n*2; i++)
    {
        while(p<=u && a[i]<a[b[u]])
        {
            u--;
        }
        b[++u]=i;
        if(i-b[p]-1==n)
        {
            p++;
        }
        if(a[i]-a[b[p]]>Max)
        {
            Max=a[i]-a[b[p]];
            s=b[p];
            k=i-s;
        }
    }
    g<<Max<<" "<<s+1<<" "<<k<<'\n';
    return 0;
}