Cod sursa(job #214211)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 13 octombrie 2008 14:25:26
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
#define N 200005
#define MIN -2000000
int v[N],s[N],p,lung,n,max=MIN,nr[N],t[N]={MIN};
void circular()
{
	int i;
	for (i=2; i<=n;++i)
		if (t[i-1]>s[i-1])
		{
			nr[i]=nr[i-1];
			t[i]=t[i-1];
		}
		else
		{
			nr[i]=i-1;
			t[i]=s[i-1];
		}
	for (i=1; i<=n;++i)
	{
		if (t[i]+s[n]-s[i-1]>max)
		{
			max=t[i]+s[n]-s[i-1];
			p=i;
			lung=n-i+1+nr[i];
		}
	}
}
void liniar()
{
	int sc=0,poz=1,i;
	for (i=2; i<=n;++i)
	{
		sc+=v[i];
		if (sc>max)
		{
			max=sc;
			p=poz;
			lung=i-poz+1;
		}
		if (sc<0)
			poz=i;
	}
}
void citire()
{
	int a,i;
	scanf("%d",&n);
	for (i=1; i<=n; ++i)
	{
		scanf("%d%d",&v[i],&a);
		if (!a)
			v[i]=-v[i];
		s[i]=s[i-1]+v[i];
	}
	circular();
}
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	citire();
	liniar();
	printf("%d %d %d\n",max,p,lung);
	return 0;
}