Cod sursa(job #216036)

Utilizator SheepBOYFelix Liviu SheepBOY Data 22 octombrie 2008 10:02:17
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 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;
	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;
	for(i=1;i<=n;i++)
	{
		sum+=v[i];
		if(sum>max)
		{
			max=sum;
			l=i-p1;
			p=p1;
		}
		if(sum<0)
		{
			sum=0;
			p1=i+1;
			//l1=0;
		}
	}
	printf("%d %d %d",max,p,l);
}

int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scan();
	maxim();
	return 0;
}