Cod sursa(job #36910)

Utilizator megabyteBarsan Paul megabyte Data 24 martie 2007 12:15:22
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#define INF "buline.in"
#define OUF "buline.out"
#define NMAX 262144
#define MAX(a,b) ((a>b)?(a):(b))
int a[NMAX],s[NMAX],best[NMAX],end[NMAX],n;
int main()
{
	FILE *in,*out;
	register int i,x,bsecv,secv,p,q;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d",&n);
	s[0]=0;best[0]=0;p=q=0;bsecv=secv=(1<<30)*(-1);
	for(i=1;i<=n;i++)
	{
		fscanf(in,"%d %d",a+i,&x);
		if(!x) a[i]*=(-1);
		s[i]=s[i-1]+a[i];
		
		if(secv+a[i]>a[i])
		{
		   secv+=a[i];
	           best[i]=best[i-1];
	        }
		else
		{
			secv=a[i];
			best[i]=i;
		}

		if(secv>bsecv) { bsecv=secv;p=best[i];q=i-p+1; }
	}
	best[0]=(1<<30)*(-1);end[0]=0;
	for(i=1;i<=n;i++)
	if(s[i]>best[i-1])
	{
		best[i]=s[i];
		end[i]=i;
	}
	else
	{
		best[i]=best[i-1];
		end[i]=end[i-1];
	}

	for(i=1;i<=n;i++)
	if(s[n]-s[i-1]+best[i-1]>bsecv)
	{
		bsecv=s[n]-s[i-1]+best[i-1];
		p=i;q=n-i+1+end[i-1];
	}

	fprintf(out,"%d %d %d",bsecv,p,q);
	fclose(in);fclose(out);
	return 0;
}