Cod sursa(job #27155)

Utilizator TabaraTabara Mihai Tabara Data 6 martie 2007 10:15:14
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>

#define in "buline.in"
#define out "buline.out"
#define NMAX 400001

int a[NMAX];
int n, smax;
int best[NMAX];

int main()
{
    freopen( in, "r", stdin );
    freopen( out, "w", stdout );
    
    scanf( "%d", &n );
    int i, col;
    for ( i = 1; i <= n; ++i )
    {
        scanf( "%d%d", &a[i], &col ); 
        if ( col == 0 ) a[i] *= -1;
    }
    
    //for ( i = 1; i <= n; printf( "%d ", a[i++] ) );    
    for ( i = 1; i <= n - 1; ++i )
    {
        a[i+n] = a[i];
    }
    //for ( i = 1; i <= 2*n-1; printf( "%d ", a[i++] ) );    
    /*
    best[0] = 0;
    smax = 0;
    int st = 1, dr = 1;
    for ( i = 1; i <= 2*n-1; ++i )
    {
        best[i] = a[i];
        if ( best[i] < best[i-1] + a[i] )
           best[i] = best[i-1] + a[i];
        if ( best[i] > smax )
           smax = best[i];
    }
    printf( "%d %d %d\n", smax, st, dr );
    */
    int s = 0; smax = 0;
	int i1 = 1, k, j;
	for ( k = 1; k <= 2*n-1; k++ )
		if ( a[k] + s > smax )
		{
			s += a[k];
			smax = s;
			i = i1;             // actualizez inceputul secventei  
			j = k;              // sfarsitul ei
		}
		else
			if ( a[k] + s > 0 ) // numerele negative se iau in secventa
				s += a[k];      // numai daca suma ei nu devine 0 sau < 0
			else
			{
				s = 0;          // caut o noua secventa
				i1 = k + 1;     // de la aceasta pozitie
			}
	printf( "%d %d %d\n", smax, i, j - i + 1 );
    return 0;
}