Cod sursa(job #329973)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 8 iulie 2009 12:34:31
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<cstdio>
#define N 400002
short int v[N];
int n,max=-N/2,pi,p=N,l=N,s[N];
void citire()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d",&n);
 	for (int i=1; i<=n; ++i)
	{
		short int c;
		scanf("%hd%hd",&v[i],&c);
		if (!c) v[i]*=-1;
		v[i+n]=v[i];
		s[i]=s[i-1]+v[i];
	}
	v[n+n]=0;
	for (int i=n+1; i<=n+n-1; ++i)
		s[i]=s[i-1]+v[i];
}
void verific(int i,int num, int sc)
{
	if (max==sc)
		if (p==i-num+1)
			if (l==num)
				return;
			else {
				if (l>num)
				{
					l=num;
					return;
				}
			}
		else
		{
			if (p>i)
			{
				p=i-num+1;
				return;
			}
		}
	else
		if (sc>max)
		{
			max=sc;
			p=i-num+1;
			l=num;
		}
}
void sume()
{
	int num=0,sc=0;
	for (int i=1; i<=n+n-1; ++i)
	{
		++num;
		sc+=v[i];
		verific(i,num,sc);
		if (sc<0) {sc=0; num=0;}
		if (num==n) {sc-=v[i-n+1]; --num;}
	}
	printf("%d %d %d",max,p,l);
}
int main()
{
	citire();
	sume();
	return 0;
}