Cod sursa(job #28798)

Utilizator megabyteBarsan Paul megabyte Data 8 martie 2007 12:02:36
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#define INF "buline.in"
#define OUF "buline.out"
#define NMAX 524288
int main()
{
	FILE *in,*out;
	int a[NMAX],sum[NMAX],pt[NMAX]={0},qt,i,j,x,n,p,max;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
        fscanf(in,"%d",&n);
	for(i=1;i<=n;i++)
	{
		fscanf(in,"%d %d",a+i,&x);
                if(!x) a[i]*=(-1);
	}
	for(i=1,j=n+1;i<=n;i++,j++) a[j]=a[i];
	sum[0]=0;p=1;qt=0;max=(1<<24)*(-1);
        for(i=1;i<2*n;i++){ sum[i]=sum[i-1]+a[i]; }
	//printf("\n");
	for(i=1;i<2*n;i++)
	{
	//	sum[i]=a[i];
		if(i-p>=n)p++;
		while(p<i&&sum[i-1]-sum[p-1]<0) p++;
		if(sum[i-1]-sum[p-1]<=0)
		{ 
			p=i;pt[i]=i;
			if(a[i]>max)  { max=a[i];qt=i; }  
		}
		else 
		{ 
			pt[i]=p; 
			x=a[i]+sum[i-1]-sum[p-1];
			if(x>max) {max=x;qt=i;}
		}
	}
	//for(i=1;i<2*n;i++) printf("%d ",sum[i]);
	//printf("\n");
	//for(i=1;i<2*n;i++) printf("%d ",pt[i]);
	fprintf(out,"%d %d %d",max,pt[qt],(qt-pt[qt]+1));
	fclose(in);fclose(out);
	return 0;
}