Cod sursa(job #491220)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 10 octombrie 2010 18:57:16
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
#define N 1<<18
int max,pi,pf,st,dr,n,k,a[N],s[N],dq[N];
void read()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    int x,c;
    scanf("%d",&n);
    k=n+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&c);
        if(c==0)
        {
            a[i]=a[n+i]=-x;
            continue;
        }
        a[i]=a[n+i]=x;
    }
    n=2*n;
}
void init()
{
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+a[i];
}
void elimst(int poz)
{
    if(poz-dq[st]>=k)
        st++;
}
void elimdr(int poz)
{
    while(s[dq[dr]]>s[poz] && dr>st)
        dq[dr]=0,dr--;
    dq[++dr]=poz;
}
void solve()
{
    max=-200000;
    dq[++st]=1;
    dr=1;
    for(int i=2;i<=n;i++)
    {
        elimst(i);
        if(s[i]-s[dq[st]]>max)
        {
            max=s[i]-s[dq[st]];
            pi=dq[st];
            pf=i;
        }
        elimdr(i);
    }
    printf("%d %d %d",max,pi+1,pf-pi);
}
int main()
{
    read();
    init();
    solve();
    return 0;
}