Cod sursa(job #404293)

Utilizator HoriaClementHoriaC HoriaClement Data 26 februarie 2010 00:08:48
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
int n,p,l;
int v[200002];
int ind[200002];
int sp[200002];
int sum[200002];

void read()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d",&n);
	int i,semn;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&v[i]);
		scanf("%d",&semn);
		if(!semn)
			v[i]=(-1)*v[i];
		sp[i]=sp[i-1]+v[i];
	}
}

void rez()
{
	int i,max=-2000000001;
	sum[1]=v[1];
	ind[1]=1;
	for(i=2;i<=n;i++)
	{
		sum[i]=sp[i];
		ind[i]=i;
		if(sum[i-1]>sum[i])
		{
			sum[i]=sum[i-1];
			ind[i]=ind[i-1];
		}
	}
	int cl=0,s=0;
	for(i=1;i<=n;i++)
		if(max<(sp[n]-sp[i]+sum[i]))
		{
			max=sp[n]-sp[i]+sum[i];
			p=i+1;
			l=n-(i-(ind[i]+1)+1);
		}
	for(i=1;i<=n;i++)
		if(s+v[i]<v[i])
		{
			s=v[i];
			cl=1;
		}
		else
		{
			cl++;
			s+=v[i]; 
			if(s>max)
			{
				max=s;
				p=i-cl+1;
				l=cl;
			}
		}
	printf("%d %d %d\n",max,p,l);
}

int main()
{
	read();
	rez();
	return 0;
}