Cod sursa(job #72419)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 13 iulie 2007 20:12:09
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 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 (int 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=a[0];
	int w=0;
	max=-2000000000;
	inc=0;
	lung=1;
	for (long i=1; i<2*n; i++)
	{
		if (a[i]>s+a[i])
		{
			w=i;
			s=a[i];
		}
		else s+=a[i];
		if (i-w+1>n)		
			s-=a[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);
	printf("%lld %d %d",max,inc+1,lung);
	fclose(stdout);
}

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