Cod sursa(job #429924)

Utilizator drywaterLazar Vlad drywater Data 30 martie 2010 16:59:13
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
FILE *f=fopen("buline.in","r"),*g=fopen("buline.out","w");
int i,n,v[400001],p,l,pm,lm,sm=-2000000000,t,s[400001],j,max[400001],poz[400001],max2[400001],poz2[400001];
int main(void)
{
	fscanf(f,"%d",&n);
	for (i=1;i<=n;i++)
	{
		fscanf(f,"%d%d",&v[i],&t);
		if (t==0)
			v[i]=v[i]*(-1);
		s[i]=s[i-1]+v[i];
		if (s[i]-max[i-1]>sm)
		{
			sm=s[i]-max[i-1];
			pm=poz[i-1]+1;
			lm=i-poz[i-1];
		}
		if (s[i]<max[i-1])
		{
			max[i]=s[i];
			poz[i]=i;
		}
		else
		{
			max[i]=max[i-1];
			poz[i]=poz[i-1];
		}
	}
	max2[n]=s[n];
	poz2[n]=n;
	for (i=n-1;i>0;i--)
	{
		if (max2[i+1]>s[i])
		{
			max2[i]=s[i];
			poz2[i]=i;
		}
		else{
			max2[i]=max2[i+1];
			poz2[i]=poz2[i+1];
		}
	}
	for (i=1;i<=n;i++)
	{
		s[i+n]=s[i+n-1]+v[i];
		if (s[i+n]-max2[i]>sm)
		{
			sm=s[i+n]-max2[i];
			pm=poz2[i]+1;
			lm=i+n-poz2[i];
		}
		
		
	}
	
	fprintf(g,"%d %d %d\n",sm,pm,lm);
	fclose(g);
	return 0;
}