Cod sursa(job #251162)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 2 februarie 2009 00:21:05
Problema Buline Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>

int a[200001],n,p,i,s[200001],smax,nr,t1,t[200001],x,maxim,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;
    }
    s[1]=a[1];
    for (i=2;i<=n;++i)
        s[i]=s[i-1]+a[i];
    for (i=1;i<=n;++i)
         a[i+n]=a[i];    
    t[1]=s[1];
    for (i=2;i<=n;++i)
        t[i]=max(s[i],t[i-1]);
    smax=0;
    nr=0;
    nrm=0;
    for (i=1;i<=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++;
        i++;
        nrm-=a[i];
    }
    
    freopen("buline.out","w",stdout);
    printf("%d %d %d",smax,poz,nr);
    return 0;
}