Cod sursa(job #179405)

Utilizator mihai0110Bivol Mihai mihai0110 Data 15 aprilie 2008 21:30:20
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#define MIN -2000000000
#define MAXN 1<<18
int i,n,sol=MIN,lg,poz,mod,sum,nou,lgnou,vechi,lgvechi;
int a[MAXN],pst[MAXN],pdr[MAXN],st[MAXN],dr[MAXN];
int main(void)
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d",&n);
	st[0]=dr[n]=MIN;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&mod);
		if(!mod)
			a[i]=-a[i];
		sum+=a[i];
		st[i]=sum;
		pst[i]=i;
		if(st[i-1]>st[i])
		{
			st[i]=st[i-1];
			pst[i]=pst[i-1];
		}
		nou=a[i];
		lgnou=1;
		if(vechi+a[i]>nou)
		{
			nou=vechi+a[i];
			lgnou=lgvechi+1;
			sol=nou;
			lg=lgnou;
			poz=i-lg+1;
		}
		vechi=nou;
		lgvechi=lgnou;
	}
	sum=0;
	for(i=n;i>0;i--)
	{
		sum+=a[i];
		dr[i]=sum;
		pdr[i]=i;
		if(dr[i+1]>dr[i])
		{
			dr[i]=dr[i+1];
			pdr[i]=pdr[i+1];
		}
	}
	for(i=1;i<n;i++)
	{
		if(st[i]+dr[i+1]>sol)
		{
			sol=st[i]+dr[i+1];
			poz=pdr[i+1];
			lg=n-pdr[i+1]+1+pst[i];
		}
	}
	printf("%d %d %d\n",sol,poz,lg);
	return 0;
}