Cod sursa(job #71156)

Utilizator a7893Nae Mihai a7893 Data 9 iulie 2007 15:58:58
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#define N 200001
int v[N],n,s[N],t[N],vf[N],poz,lg;
void read()
{
	int i,nrb,color;
	scanf("%d",&n);
	for(i=0;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=0;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;
}		
void solve()
{
	int i,s_max,sum=0,nr=0,poz_f;
	s[0]=v[0];
	for(i=1;i<n;i++)
		s[i]=s[i-1]+v[i];
	//afis(s);
	t[0]=s[0];
	for(i=1;i<n;i++)
		t[i]=max(s[i-1],s[i]);
	//afis(t);
	for(i=1;i<n;i++)
		vf[i]=t[i-1]+s[n-1]-s[i-1];
	//afis(vf);
	s_max=v_max(vf);
	poz_f=poz;
	sum=v[poz];
	nr=1;
	while(sum<s_max)
	{
		poz++;
		if(poz==n)
			poz=0;
		sum+=v[poz];
		nr++;
	}
	printf("%d %d %d\n",s_max,poz_f+1,nr);
}
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	read();
	solve();
	return 0;
}