Cod sursa(job #503524)

Utilizator PavelPavel Ana-Oriana Pavel Data 23 noiembrie 2010 15:57:40
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>

using namespace std;

ifstream in("buline.in");
ofstream out("buline.out");

int v[200001];

int main()
{
	int n,x,i,y,sc=0,smax=-1000000000,start,amax,lmax,lmin,smin=9999,amin,stot=0,lung;
	in>>n;
	stot=0;
	for(i=1;i<=n;i++)
	{
		in>>x>>y;
		if(y==1)
		{
			v[i]=x;
			stot+=x;
		}
		else
		{
			v[i]=-x;
			stot-=x;
		}
	}
	sc = -1;
	start = 1;
	lung = 0;
	for(i=1;i<=n;i++)
	{
		if(sc <= 0)
		{
			start = i;
			sc = 0;
			lung = 0;
		}
		sc += v[i];
		++lung;
		if(sc > smax || (sc == smax && lung < lmax))
		{
			smax = sc;
			amax = start;
			lmax = lung;
		}
	}
	sc = 0;
	start = 1;
	lung = 0;
	for(i=1;i<=n;i++)
	{
		if(sc > 0)
		{
			start = i;
			sc = 0;
			lung = 0;
		}
		sc += v[i];
		++lung;
		if(sc<smin ||(sc == smin && lung>lmin))
		{
			smin=sc;
			amin=start;
			lmin=lung;
		}
	}
	if(smax>stot-smin)
		out<<smax<<' '<<amax<<' '<<lmax<<'\n';
	else
		out<<stot - smin<<' '<<amin + lmin<<' '<<n - lmin<<'\n';
	return 0;
}