Cod sursa(job #165854)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 27 martie 2008 00:05:08
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#define N 200111
int n,sum=0,s,l,sb,e,lb,max=-N;
struct bila{
	int a,b;
};
bila v[N];
void scan()
{
	freopen("buline.in", "r",stdin);
	freopen("buline.out", "w",stdout);
	scanf("%d", &n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d", &v[i].a,&v[i].b);
		if(!v[i].b)
			v[i].b=-1;
	}	
}
void solve()
{
	sum=0; 
	s=1;
	for(int k=1;k<=2;++k)
	for(int	i=1;i<=n;++i)
	{
		if(k==2 && i==n)
			break;
		e=i;
		if(sum<0)
		{
			sum=0;
			s=i;
			if(s>n)
				s=1;
		}
		sum+=v[i].a*v[i].b;
		if(e>=s && k==1)
				l=e-s+1;
			else
				l=(n-s)+e+1;
		if(l>n)
		{sum-=v[s].a*v[s].b; ++s;}	
		if(sum>max)
		{
			max=sum;
			sb=s;
			lb=l;
		}
	//printf("%d %d %d %d\n",sum,s,e,l);
	}
	printf("%d %d %d\n",max,sb,lb);
}
int main()
{
	scan();
	solve();
	return 0;
}