Cod sursa(job #27426)

Utilizator TabaraTabara Mihai Tabara Data 6 martie 2007 14:02:17
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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, nrsol, real;
int sum, 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;
        sum += a[i];
    }
    
    for ( i = 1; i <= n; ++i )
    {
        a[i] *= -1;
    }
    
    smax = 0;
    int poz;
    
    for ( i = 1; i <= n; ++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];
             poz = i;
        }
    }
    
    nrsol = sum - (-1)*(smax);
    printf( "%d %d %d\n", nrsol, poz, poz + 1);
       
    return 0;
}