Cod sursa(job #1357005)

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

#define Nmax 200001
#define inf 2000000000

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

int v[2*Nmax];

int main(){
	int N, x, y, sum = 0, smax = -inf, st = 1, dr = 1, sts, drs;
	
	fscanf ( f, "%d", &N );
	
	for ( int i = 1; i <= N; ++i ){
		fscanf ( f, "%d%d", &x, &y );
		if ( y == 0 )
			v[i] = v[i+N] = -x;
		else
			v[i] = v[i+N] = x;
		
		if ( v[i] > smax ){
			smax = v[i];
			sts = i;
			drs = i;
		}
	}
	
	if ( smax <= 0 ){
		fprintf ( g, "%d %d %d", smax, st, 1 );
		return 0;
	}
	
	int cN = ( N << 1 );
	
	for ( int i = 1; i <= cN; ++i ){
		if ( i - st + 1 > N )
			break;
		
		if ( sum + v[i] < 0 ){
			sum = 0;
			st = i + 1;
			dr = st;
		}
		else{
			sum += v[i];
			dr = i;
		}
		
		if ( sum > smax ){
			smax = sum;
			sts = st;
			drs = dr;
		}
		else{
			if ( sum == smax && st < sts ){
				sts = st;
				drs = dr;
			}
		}
	}
	
	fprintf ( g, "%d %d %d", smax, sts, drs - sts + 1 );
	
	return 0;
}