Cod sursa(job #393334)

Utilizator loginLogin Iustin Anca login Data 9 februarie 2010 11:35:36
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
# include <fstream>
using namespace std;
int v[400003], n, sol=-1000000000;

void read ()
{
	ifstream fin ("buline.in");
	fin>>n;
	int nrb, c;
	for (int i=1;i<=n;i++)
	{
		fin>>nrb>>c;
		if (c==1) v[i]=nrb;
		else v[i]=-nrb;
		v[n+i]=v[i];
	}
}

void ssm ()
{
	int dq[200000], p[200000], st, dr;
	int scur, smin, x, y;
	scur=smin=v[1];
	x=y=1;
	st=dr=1;
	dq[st]=smin;
	p[st]=1;
	for (int i=2;i<2*n;i++)
	{
		scur+=v[i];
		if (scur-dq[st]>sol)
			sol=scur-dq[st], x=p[st], y=i;
		while (dr>=st && scur<dq[dr])dr--;
		dq[++dr]=scur, p[dr]=i;
		if (i-p[st]==n)
			st++;
	}
	ofstream fout ("buline.out");
	fout<<sol<<" "<<x+1<<" "<<y-x;
}

int main ()
{
	read ();
	ssm ();
	return 0;
}