Cod sursa(job #462552)

Utilizator SpiderManSimoiu Robert SpiderMan Data 11 iunie 2010 15:09:35
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>

const char FIN[] = "buline.in", FOU[] = "buline.out";
const int MAX = 200006;

int V[MAX], Suma[MAX], best[MAX] = { 0 , 1 } ;
int N, S, P, L ;

int main ()
{
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    scanf("%d", &N);

    for (int i = 1, nr = 0, cul = 0; i <= N; ++i)
    {
        scanf ( "%d %d", &nr, &cul ) ;
        Suma[ i ] = Suma[ i - 1 ] + ( V[ i ] = cul ? nr : -nr ) ;
    }

    int S = V[N], P = N, L = 1;

    for (int i = N - 1, s = V[N], p = N; i ; --i)
    {
        ( s += V[ i ] ) <= V[ i ] ? s = V[ i ], p = i : 0 ;
        S <= s ? S = s, P = i, L = p - i + 1 : 0;
    }

    for (int i = 2; i <= N; ++i)
        Suma[ best[ i - 1 ] ] < Suma[ i ] ? best[ i ] = i : best[ i ] = best[ i - 1 ] ;

    for (int s = 0, i = N, p = 0; i ; --i)
        S < ( p = ( s += V[ i ] ) + Suma[ best[ i - 1 ] ] ) || ( S == p && P > i ) ?  S = p, P = i, L = N - i + 1 + best[ i - 1 ] : 0 ;


    printf("%d %d %d", S, P, L);

    return 0;
}