Cod sursa(job #813469)

Utilizator predatorGigi Valoare predator Data 15 noiembrie 2012 16:36:09
Problema Buline Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,i,x,s,v[200010],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];
	}
	for(i=n+1;i<=2*n;++i)
	{
		v[i]=v[i-1]+t[i%n];
	}
	front=1; back=0;
	front1=1; back1=0;
	for(i=1;i<=2*n;++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]+l-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;
}