Cod sursa(job #503518)

Utilizator theocmtAxenie Theodor theocmt Data 23 noiembrie 2010 15:32:49
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<cstdio>

using namespace std;

int x,y,v[200000],sc=0,sc2=0,smax=-1000000,smin=100000,p=1,p1=1,p2=1,pp1=1,pp2=1,pp=1,sab=0,ss=0,n,lmin=0;
int main()
{
	int i;
	freopen("buline.in","r",stdin);
	freopen("buline.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d %d",&x,&y);
		if (y==0)
			v[i]=-x;
		if (y==1)
			v[i]=x;
		sc+=v[i];
		if (sc>smax)
		{
			p1=p;
			p2=i;
			smax=sc;
		}
		if (sc<=0)
		{
			sc=0;
			p=i+1;
		}
		sc2+=v[i];
		if (sc2<smin)
		{
			pp1=pp;
			pp2=i;
			smin=sc2;
		}
		if (sc2>=0)
		{
			sc2=0;
			pp=i+1;
		}
		sab += v[i];
	}
	ss=sab-smin;
	lmin = pp2-pp1+1;
	//printf("%d\n%d\n",sab,smin);
	if (sc>ss)
		printf("%d %d %d\n",smax,p1,p2-p1+1);
	else
		printf("%d %d %d\n",ss,pp2+1,pp1+lmin);
	return 0;
}