Cod sursa(job #71155)

Utilizator a7893Nae Mihai a7893 Data 9 iulie 2007 15:53:16
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#define N 200001
int v[N+N],n,s[N+N],t[N+N],pozitie,lungime;
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;
	}
}
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
void solve()
{
	int sum_max,sum_c,ic,sf,poz_ic,i,n1;
	n1=n;
	for(i=0;i<n1-1;i++)
		v[n++]=v[i];
	sum_max=v[0];
	sum_c=sum_max;
	poz_ic=0;
	ic=sf=0;
	for(i=1;i<n;i++)
	{
		if(sum_c<0)
		{
			sum_c=v[i];
			poz_ic=i;
		}
		else
			sum_c+=v[i];
		if(sum_max<sum_c)
		{
			sum_max=sum_c;
			ic=poz_ic;
			sf=i;
		}
	}
	printf("%d %d %d\n",sum_max,ic+1,sf-ic+1);
}
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	read();
	solve();
	return 0;
}