Cod sursa(job #1412175)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 1 aprilie 2015 10:11:36
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
int bul[400005];
int main()
{
    freopen( "buline.in", "r", stdin );
    freopen( "buline.out", "w", stdout );
    int n, i, cul, sc, st, smax, stm, drm, stot, sc1, st1, smax1, stm1, drm1;
    scanf( "%d", &n );
    for( i=1; i<=n; i++ )
    {
        scanf( "%d%d", &bul[i], &cul );
        if( cul==0 )
            bul[i]=0-bul[i];
        stot=stot+bul[i];
        bul[n+i]=bul[i];
    }
    sc=smax=bul[1];
    st=stm=drm=1;
    for( i=2; i<=2*n-1; i++ )
    {
        if( sc+bul[i]>bul[i] )
            sc=sc+bul[i];
        else
            sc=bul[i], st=i;
        if( sc>smax )
            stm=st, drm=i, smax=sc;
    }
    if( drm-stm+1<=n )
        printf( "%d %d %d", smax, (stm-1)%n+1, drm-stm+1 );
    else
    {
        sc1=smax1=bul[1];
        st1=stm1=drm1=1;
        for( i=2; i<=2*n-1; i++ )
        {
            if( sc1+bul[i]<bul[i] )
                sc1=sc1+bul[i];
            else
                sc1=bul[i], st1=i;
            if( sc1<smax1 )
                stm1=st1, drm1=i, smax1=sc1;
        }
        printf( "%d %d %d", stot-smax1, (drm1+1)%n+1, n-(drm1-stm1+1) );
    }
    return 0;
}