Cod sursa(job #425299)

Utilizator Cristi09Cristi Cristi09 Data 25 martie 2010 17:10:08
Problema Buline Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>
int n,a[400000],max,st,fn;
void read()
{
	FILE*f=fopen("buline.in","r");
	fscanf(f,"%d",&n);
	int i,var,aux;
	for(i=0;i<n;++i)
	{
		fscanf(f,"%d%d",&var,&aux);
		a[i]=a[n+i]=var;
		if(!aux)a[i]=a[n+i]=-var;
	}
	fclose(f);
}
void func()
{
	int var=0,i,min=0,minP=-1;
	st=-1;
	
	for(i=0;i<n+n;++i)
	{
		if(i-minP>=n)
		{
			++minP;
			min+=a[minP];
			var=min;
			i=minP+1;
		}
		var+=a[i];
		if(var-min>max)
		{
			max=var-min;
			st=minP+1;
			fn=i;
		}
		if(var<min)
		{
			min=var;
			minP=i;
		}		
	}
}
int main()
{
	read();
	func();
	FILE*g=fopen("buline.out","w");
	fprintf(g,"%d %d %d\n",max,st+1,fn-st+1);
	fclose(g);
	return 0;
}