Cod sursa(job #25006)

Utilizator 004444Lapusan Tudor 004444 Data 4 martie 2007 09:31:01
Problema Buline Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasa a 9-a si gimnaziu Marime 1.26 kb
#include <stdio.h>
#define MAX 4002


int n, ip, is, s_max;
int a[MAX];


void citire ();
void dinamica ();
void afisare ();


int main ()
{
    freopen ( "buline.in", "r", stdin );
    freopen ( "buline.out", "w", stdout );

    citire ();
    dinamica ();
    afisare ();

    return 0;
}

void citire ()
{
    int i, x, y;

    scanf ( "%d", &n );
    for ( i = 1; i <= n; i++ )
    {
        scanf ( "%d %d", &x, &y );
        if ( y == 1 )
            a[i] = x;
        else
            a[i] = -x;
//        printf ( "%d %d\n", x, y );
    }
    //    scanf ( "%d", &a[i] );
    for ( i = n + 1; i <= 2 * n; i++ )
        a[i] = a[i - n];
//    for ( i = 1; i <= 2 * n; i++ )
//        printf ( "%d ", a[i] );
}

void dinamica ()
{
    int i, suma, ii;

    suma = 0;
    ii = 1;
    for ( i = 1; i <= 2 * n; i++ )
    {
        suma += a[i];

        if ( ip <= i - n )
            break;
        if ( suma > s_max )
        {
            s_max = suma;
            ip = ii;
            is = i;
        }
        else
        if ( suma < 0 )
        {
            ii = i + 1;
            suma = 0;
        }
    }
}
            
void afisare ()
{   
    printf ( "%d %d %d\n", s_max, ip, is - ip + 1 );
}