Cod sursa(job #71218)

Utilizator a7893Nae Mihai a7893 Data 9 iulie 2007 20:09:01
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<stdio.h>
#define N 200001
int v[N],n,s[N],t[N],vf[N],poz,lg,s_max;
void read()
{
	int i,nrb,color;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&nrb,&color);
		if(color==0)
			v[i]=-nrb;
		else
			v[i]=nrb;
	}
}
void afis(int a[N])
{
	int i;
	for(i=1;i<=n;i++)
		printf("%d ",a[i]);
	printf("\n");
}
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int v_max(int v[N])
{
	int i,max;
	max=v[1];
	for(i=1;i<=n;i++)
		if(v[i]>max)
		{
			max=v[i];
			poz=i;
		}
	return max;
}		
int mul(int vf[N])
{
	int nr=0,i;
	for(i=1;i<=n;i++)
		if(vf[i]==s_max)
			nr++;
	if(nr>1)
		return 1;
	return 0;
}
int lungime(int poz)
{
	int nr,sum;
	sum=v[poz];
	nr=0;
	while(sum!=s_max)
	{
		poz++;
		if(poz==n+1)
			poz=0;
		sum+=v[poz];
		nr++;
	}
	return nr;
}
void solve()
{
	int i,poz_f,nr,max2;
	s[1]=v[1];
	for(i=2;i<=n;i++)
		s[i]=s[i-1]+v[i];
	//afis(v);
	//afis(s);
	t[1]=s[1];
	for(i=2;i<=n;i++)
		t[i]=max(t[i-1],s[i]);
	//afis(t);
	for(i=1;i<=n;i++)
		vf[i]=t[i-1]+s[n]-s[i-1];
	//afis(vf);
	s_max=v_max(vf);
	poz_f=poz;
	nr=lungime(poz);
	max2=N;
	if(!mul(vf))
	{
		printf("%d %d %d\n",s_max,poz_f,nr);
		return;
	}
	else
		for(i=1;i<=n;i++)
			if(vf[i]==s_max&&lungime(i)<max2)
			{
				poz_f=i;
				max2=lungime(i);
			}
	printf("%d %d %d\n",s_max,poz_f,max2);
}
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	read();
	solve();
	return 0;
}