Cod sursa(job #216034)

Utilizator SheepBOYFelix Liviu SheepBOY Data 22 octombrie 2008 09:55:12
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#define N 200200
int n,v[N],t[N],sum[N],lung[N];
void scan()
{
	int x;
	scanf("%d%d%d",&n,v+1,&x);
	if(!x)
		v[1]=-v[1];
	sum[1]=v[1];
	t[1]=0;
	for(int i=2;i<=n;i++)
	{
		scanf("%d%d",v+i,&x);
		if(!x)
			v[i]=-v[i];
		sum[i]=sum[i-1]+v[i];
		if(t[i-1]>sum[i-1])
		{
			t[i]=t[i-1];
			lung[i]=lung[i-1];
		}
		else
		{
			t[i]=sum[i-1];
			lung[i]=i-1;
		}
	}
}
void maxim()
{
	int i,l,p,max=-10000,mx=-10000;
	for(i=1;i<=n;i++)
	{
		if(t[i]+sum[n]-sum[i-1]>max)
		{
			max=t[i]+sum[n]-sum[i-1];
			p=i;
			l=n-i+1+lung[i];
		}
	}
	int sum=0,p1=1,l1;
	for(i=1;i<=n;i++)
	{
		sum+=v[i];
		if(sum>max)
		{
			max=sum;
			l1=i-p1;
		}
		if(sum<0)
		{
			sum=0;
			p1=i;
			l1=0;
		}
	}
	if(max>mx)
		printf("%d %d %d",max,p,l);
	else
		printf("%d %d %d",mx,p1,l1);
}
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scan();
	maxim();
	return 0;
}