Cod sursa(job #71153)

Utilizator a7893Nae Mihai a7893 Data 9 iulie 2007 15:38:03
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#define N 200001
int v[N],n,s[N],t[N],pozitie,lungime;
struct vec{
	int m,lg;
}vf[N];
void read()
{
	int i,nrb,color;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&nrb,&color);
		if(color==0)
			v[i]=-nrb;
		else
			v[i]=nrb;
	}
}
void afis(int a[N])
{
	int i;
	for(i=0;i<n;i++)
		printf("%d ",a[i]);
	printf("\n");
}
int max(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
int v_max(vec v[N])
{
	int i,maxim;
	maxim=v[1].m;
	for(i=1;i<n;i++)
		if(v[i].m>maxim)
		{
			maxim=v[i].m;
			lungime=v[i].lg;
			pozitie=i+1;
		}
	return maxim;
}		
void solve()
{
	int i,s_max;
	s[0]=v[0];
	for(i=1;i<n;i++)
		s[i]=s[i-1]+v[i];
	//afis(v);
	//afis(s);
	t[0]=s[0];
	for(i=1;i<n;i++)
		t[i]=max(s[i-1],s[i]);
	//afis(t);
	for(i=1;i<n;i++)
	{
		vf[i].m=t[i-1]+s[n-1]-s[i-1];
		vf[i].lg=i-1+n-1-(i-1);
	}
	//afis(vf);
	s_max=v_max(vf);
	printf("%d %d %d\n",s_max,pozitie,lungime);
}
int main()
{
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	read();
	solve();
	return 0;
}