Cod sursa(job #433088)

Utilizator Cristi09Cristi Cristi09 Data 3 aprilie 2010 12:45:01
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
int n,a[200001],max=-999999999,st,fn,s[200001],t[200001];
int MAX(int a,int b)
{
	if(a>=b)return a;
	return b;
}

void read()
{
	FILE*f=fopen("buline.in","r");
	fscanf(f,"%d",&n);
	int i,var,aux;
	//s[0]=-999999999;
	for(i=1;i<=n;++i)
	{
		fscanf(f,"%d%d",&var,&aux);
		a[i]=var;
		if(!aux)a[i]=-var;
		
		s[i]=s[i-1]+a[i];
		if(s[t[i-1]]>=s[i]&&i!=1)
		t[i]=t[i-1];
		else t[i]=i;
	}
	fclose(f);
}
void func()
{
	int i;
	st=-1;
	
	for(i=1;i<=n;++i)
	{
		if(s[t[i-1]]+s[n]-s[i-1]>max)
		{
			max=s[t[i-1]]+s[n]-s[i-1];
			st=i;
			if(t[i-1]<i)fn=n+t[i-1];
			else fn=t[i-1];
		}
		if(s[i]-s[t[i-1]-1]>max)
		{
			max=s[i]-s[t[i-1]-1];
			st=t[i-1]-1;
			fn=i-st;
		}
		if(a[i]>max)
		{
			max=a[i];
			st=i;fn=i;
		}
	}
}
int main()
{
	read();
	func();
	FILE*g=fopen("buline.out","w");
	fprintf(g,"%d %d %d\n",max,st,fn-st+1);
	fclose(g);
	return 0;
}