Cod sursa(job #27916)

Utilizator webspiderDumitru Bogdan webspider Data 7 martie 2007 11:53:05
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int sir[200001];

int c[] = { -1, 1 };
int st, end;
int sum=-1000000,sumc,ps,l;
int cc=-1000000,cd;

int n;
int asd;

int main()
{
	int a,b,i;
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);

	scanf("%d\n", &n );

	for ( i = 1; i <= n; i++ )
	{
		scanf("%d %d\n", &a, &b );
		sir[i] = a * c[b];
		if ( b == 0 )
		{
			if ( sir[i] > cc )
			{
				cc = sir[i];
				l = 1;
				ps = i;
			}
			cd ++;
		}
	}
	if ( cd == n )
	{
		printf("%d %d %d\n", cc, ps, l);
		return 0;
	}

	l = ps = 0;
	st = end = 1;
	sumc = sir[1];

	while ( 1 )
	{
		while ( sumc <= 0 ) 
		{	
			if ( end <  st ) break;
			st = end+1;
			sumc = sir[st];
			end = st;
		}
		if ( sumc > sum )
		{
			sum = sumc;
			ps = st;
			if ( asd )
				l = ( n - st + 1 ) + end;
			else
				l = end - st + 1;
		}

		if ( end == n )
		{
			end=1;
			sumc+=sir[end];		
			asd = 1;
		}
		else
		{
			end++;
			sumc+=sir[end];
		}
		if ( end == st ) break;
		
	}

	printf("%d %d %d\n", sum, ps, l );

	fclose(stdin);
	fclose(stdout);

	return 0;
}