Cod sursa(job #813487)

Utilizator predatorGigi Valoare predator Data 15 noiembrie 2012 16:48:52
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,i,x,s,v[400010],t[200010],poz1,L,p2,p3,pl,DM[200010],Dm[200010],l,p1,back,back1,front,front1;
int main ()
{
	f>>n;
	int max=-1<<15;
	for(i=1;i<=n;++i)
	{
		f>>t[i]>>s;
		v[i]=v[i-1];
		if(!s)
			t[i]=-t[i];
		v[i]+=t[i];
		if(t[i]>max)
		{
			max=t[i];
			p2=i-1;
			L=2;
		}
	}
	for(i=n+1;i<=2*n;++i)
	{
		v[i]=v[i-1]+t[i%n];
	}
	front=1; back=0;
	front1=1; back1=0;
	++n;
	for(i=0;i<=2*n-2;++i)
	{
		while(front<=back&&v[i]<=v[Dm[back]]) --back;
		Dm[++back]=i;
		
		if(Dm[front]==i-n)
		 ++front; 
		if(v[i]-v[Dm[front]]>max)
		{
			max=v[i]-v[Dm[front]];
			p1=i; p2=Dm[front];
			L=p1-p2+1;
			if(L<0)
				L+=n;
		}
	}
	g<<max<<" "<<p2+1<<" "<<L-1;
	return 0;
}