Cod sursa(job #839116)

Utilizator stoicatheoFlirk Navok stoicatheo Data 21 decembrie 2012 12:47:36
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,i,x,s,v[400010],t[200010],poz1,L,p2,p3,pl,DM[200010],Dm[200010],l,p1,back,back1,front,front1;
int main ()
{
    f>>n;
    int max=-1<<15;
    for(i=1;i<=n;++i)
    {
        f>>t[i]>>s;
        v[i]=v[i-1];
        if(!s)
            t[i]=-t[i];
        v[i]+=t[i];
        if(t[i]>max)
        {
            max=t[i];
            p2=i-1;
            L=2;
        }
    }
    for(i=n+1;i<=2*n;++i)
    {
        v[i]=v[i-1]+t[i%n];
    }
    front=1; back=0;
    front1=1; back1=0;
    ++n;
    for(i=0;i<=2*n-2;++i)
    {
        while(front<=back&&v[i]<=v[Dm[back]]) --back;
        Dm[++back]=i;
         
        if(Dm[front]==i-n)
         ++front; 
        if(v[i]-v[Dm[front]]>max)
        {
            max=v[i]-v[Dm[front]];
            p1=i; p2=Dm[front];
            L=p1-p2+1;
            if(L<0)
                L+=n;
        }
    }
    g<<max<<" "<<p2+1<<" "<<L-1;
    return 0;
}