Cod sursa(job #72441)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 13 iulie 2007 20:56:59
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<stdio.h>
#define val 400003

long n;
long long max;
int a[val],inc,lung;

void citire()
{
	freopen("buline.in","r",stdin);
	scanf("%ld", &n);
	int w;
	for (long i=0; i<n; i++)
	{
		scanf("%d%d", &a[i], &w);
		if (w==0)
			a[i]*=-1;
		a[i+n]=a[i];
	}
	fclose(stdin);
}

void prelucrare()
{
	long long s=-2000;//a[0];
	int w=0;
	max=-2000000000;
//	inc=0;
//	lung=1;
	for (long i=0; i<2*n; i++)
	{
		if (a[i]>s+a[i])
		{
			w=i;
			s=a[i];
		}
		else s+=a[i];
		while (i-w+1>n)		
		{
			//s-=a[w];
			s-=a[i];
			++w;
        }
		if (s>max)
		{
			inc=w;
			lung=i-w+1;
			max=s;
		}
/*		else if (s==max && inc>w)
		{
			inc=w;
			lung=i-w+1;
			max=s;
		}
		else if (s==max && inc==w && lung>i-w+1)
		{
			inc=w;
			lung=i-w+1;
			max=s;
		}

*/
	}
}

void printare()
{
	freopen("buline.out","w",stdout);
	++inc;
	inc%=n;
	printf("%lld %d %d",max,inc,lung);
	fclose(stdout);
}

int main()
{
	citire();
	prelucrare();
	printare();
	return 0;
}