Cod sursa(job #1357199)

Utilizator BLz0rDospra Cristian BLz0r Data 23 februarie 2015 20:14:07
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
using namespace std;

#define Nmax 200002
 
FILE *f = fopen ( "buline.in", "r" );
FILE *g = fopen ( "buline.out", "w" );

int v[Nmax];
int sum[Nmax], smax[Nmax], idx[Nmax];
 
int main(){
	int N, s = 0, st, x, sol = 0, poz, lg; 
	
    fscanf ( f, "%d ", &N );
    
    for ( int i = 1; i <= N; ++i ){
        fscanf ( f, "%d%d", &v[i], &x );
        if ( x == 0 )
			v[i] = -v[i];
    }
	
    for ( int i = 1; i <= N; ++i )
		sum[i] = sum[i-1] + v[i];
    
    for ( int i = 1; i <= N; ++i ) 
		if ( smax[i-1] > sum[i] ){
			smax[i] = smax[i-1];
			idx[i] = idx[i-1];
		}
		else {
			smax[i] = sum[i];
			idx[i] = i;
		}
	
    for ( int i = 1; i <= N; ++i ){
        if ( s <= 0){
            s = 0;
            st = i;
        }
        s += v[i];
        
		if ( s > sol ) {
			sol = s;
			poz = st;
			lg = i - st + 1;
        } 
    }
	
    for ( int i = 1; i <= N; ++i )
		if ( sum[N] - sum[i-1] + smax[i-1] > sol ){
			sol = sum[N] - sum[i-1] + smax[i-1];
			poz = i;
			lg = N + idx[i-1] - i + 1;
		}
	
    fprintf ( g, "%d %d %d", sol, poz, lg );
	
    return 0;
}