Cod sursa(job #47956)

Utilizator crusRus Cristian crus Data 4 aprilie 2007 11:34:51
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#define input "buline.in"
#define output "buline.out"
#define nmax 200001
long v[nmax],l[nmax],st,max,i,cnt[nmax],n,b,lung,s[nmax],t[nmax];
void citire()
{
	FILE *fin;
	fin=fopen(input,"r");
	fscanf(fin,"%ld",&n);
	for (i=1;i<=n;i++)
		{
		 fscanf(fin,"%ld %ld",&v[i],&b);
		 if (!b) v[i]=-v[i];
		 v[i+n]=v[i];
		}	
	fclose(fin);
}
void solve()
{	
	cnt[1]=v[1];
	l[1]=1;
	max=cnt[1];
	st=1;
	lung=1;
	s[1]=cnt[1];
	t[1]=cnt[1];
	for (i=2;i<=n;i++)
		{
		 if (cnt[i-1]>0) 
			{
			 cnt[i]=v[i]+cnt[i-1];
			 l[i]=l[i-1]+1;
			}
		    else
			{
			 cnt[i]=v[i];
			 l[i]=1;
			}
		 if (cnt[i]>max)
			{
			 max=cnt[i];
			 st=i-l[i]+1;
			 lung=l[i];
			}
		 s[i]=s[i-1]+v[i];
		 if (s[i]>t[i-1]) t[i]=s[i];
		    else t[i]=t[i-1];
		}
	for (i=1;i<=n;i++)
		if (t[i-1]+s[n]-s[i-1]>max) max=t[i-1]+s[n]-s[i-1];
}
void afisare()
{
	FILE *fout;
	fout=fopen(output,"w");
	fprintf(fout,"%ld %ld %ld",max,st,lung);
	fclose(fout);
}
int main()
{
	citire();
	solve();
	afisare();
	return 0;
}