Cod sursa(job #51453)

Utilizator cos_minBondane Cosmin cos_min Data 12 aprilie 2007 22:51:43
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>

#define in "buline.in"
#define out "buline.out"
#define dim 200001

int A[2*dim], best[2*dim], Nr[2*dim], part[2*dim];
int N;

int main()
{
    int a, b;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d", &N);
    
    part[0] = 0;
    
    for ( int i = 1; i <= N; i++ )
    {
        scanf("%d%d", &a, &b); 
        if ( b == 1 ) A[i] = a, A[N+i] = a;
        else          A[i] = -a, A[N+i] = -a;
    }
    
    for ( int i = 1; i <= 2*N; i++ ) part[i] = part[i-1] + A[i];
    
    best[1] = A[1];
    Nr[1] = 1;
    
    for ( int i = 2; i <= 2*N; i++ )
    {
        best[i] = A[i];
        Nr[i] = i;
        if ( best[i] < A[i] + best[i-1] && i - Nr[i-1] < N ) best[i] = A[i] + best[i-1], Nr[i] = Nr[i-1];
    }
    
    for ( int i = N+1; i <= 2*N; i++ )
        if ( best[i] < part[i] - part[i-N+1] ) best[i] = part[i] - part[i-N+1], Nr[i] = i-N+1;
    
    int maxim = -1000000;
    int p;
    
    for ( int i = 1; i <= 2*N; i++ )
    {
       // printf("%d ", A[i]);
        if ( maxim < best[i] ) maxim = best[i], p = i;
    }
    
    printf("%d %d %d", maxim, Nr[p], p-Nr[p]+1 );
}