Cod sursa(job #458147)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 23 mai 2010 14:04:12
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb

#include <stdio.h>

int a[400201],n,i,s[402001],smax,nr,t1,t[400201],x,poz,nrm;

int max(int a, int b)
{
    if (a>b) return a;
    return b;
}

int main()
{
    freopen("buline.in","r",stdin);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d %d",&x,&t1);
        if (t1==0)
            a[i]=-x;
            else
            a[i]=x;
    }
    for (i=1;i<=n;++i)
         a[i+n]=a[i];
    s[1]=a[1];
    for (i=2;i<=2*n;++i)
        s[i]=s[i-1]+a[i];
    t[1]=s[1];
    for (i=2;i<=2*n;++i)
        t[i]=max(s[i],t[i-1]);
    smax=0;
    for (i=1;i<=2*n;++i)
         if (t[i-1]+s[n]-s[i-1]>=smax)
             {
             smax=t[i-1]+s[n]-s[i-1];
             poz=i;
             }
    i=poz;
    nr=1;
    nrm=smax-a[poz];
    while(nrm!=0)
    {
        nr++;
        nrm-=a[++i];
    }
    
    freopen("buline.out","w",stdout);
    printf("%ld %ld %ld",smax,poz,nr);
    return 0;
}