Cod sursa(job #458014)

Utilizator edp100Edp100 edp100 Data 22 mai 2010 17:26:35
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<stdio.h>

int v[200005],inc;
int s,smax,sol,n;
int p1,p2,lg1,lg2;


int main ()
{
    int tip,i;
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i],&tip);
        if(!tip)
            v[i]*=-1;
    }
    inc=1;
    for(i=1;i<=n;i++)
    {
        s+=v[i];
        if(s<0)
        {
            s=0;
            inc=i+1;
            continue;
        }
        if(s>smax)
        {
            smax=s;
            p1=inc;lg1=i-p1+1;
        }
    }
    s=0;inc=1;
    sol=smax;
    smax=0;
    for(i=1;i<=n;i++)
    {
        s+=v[i];
        if(s>0)
        {
            s=0;
            inc=i+1;
            continue;
        }
        if(s<smax)
        {
            smax=s;
            p2=i+1;lg2=inc+n-p2;
        }
    }
    smax=-smax;
    for(i=1;i<=n;i++)
        smax+=v[i];
    if(sol>smax)
    {
        printf("%d %d %d\n",sol,p1,lg1);
        return 0;
    }
    if(sol<smax)
    {
        printf("%d %d %d\n",smax,p2,lg2);
        return 0;
    }
    //////////////
    if(p1>p2)
    {
        printf("%d %d %d\n",sol,p1,lg1);
        return 0;
    }
    
    if(p1<p2)
    {
        printf("%d %d %d\n",smax,p2,lg2);
        return 0;
    }
    ////////////////
    
    if(lg1>lg2)
    {
        printf("%d %d %d\n",sol,p1,lg1);
        return 0;
    }
    printf("%d %d %d\n",smax,p2,lg2);
    return 0;
}