Cod sursa(job #27168)

Utilizator TabaraTabara Mihai Tabara Data 6 martie 2007 10:33:54
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>

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

#define maxim(a,b) ( (a) > (b) ? (a) : (b) )

int a[NMAX];
int n, smax;
int sum[NMAX], tata[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;
    }
    sum[1] = a[1];
    tata[1] = a[1];
    
    for ( i = 2; i <= n; ++i )
    {
        sum[i] = sum[i-1] + a[i];
        tata[i] = maxim( sum[i], tata[i-1] );
    }
    
    /*for ( i = 1; i <= n; ++i )
    {
        printf( "%d ", sum[i] );
        printf( "%d\n", tata[i] );
    }
    */
    int best, poz;
    for ( i = 1; i <= n; ++i )
    {
        best = sum[n] + tata[i-1] - sum[i-1];
        if ( best > smax )
        {
             smax = best;
             poz = i;
        }
    }
    
    printf( "%d %d %d\n", smax, poz, poz+1 );    
    //for ( i = 1; i <= n; printf( "%d %d\n", sum[i++], tata[i++]) );
       
    return 0;
}