Cod sursa(job #800911)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 22 octombrie 2012 21:31:22
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#define dim 400002
using namespace std;


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

int v[dim],n,x,o,i,end,deque[dim],begin,idx,front,back;
long long Max,S[dim];
int main () {
	
	f>>n;
	
	for(i=1;i<=n;++i){
		f>>x>>o;
		if(o==0)
			x=-x;
		v[i+n]=v[i]=x;
	}
	
	for(i=1;i<=2*n ;++i){
		
		S[i]=S[i-1]+v[i];
		
	}
	
	front=1;back=0;
	begin=1;
	end=n;
	Max=S[n];
	for(i=1;i<=2*n;++i){
		
		while (front<=back && deque[front]<i-n)
			++front;
		
		if(Max<S[i]-S[deque[front]]){
			
			Max=S[i]-S[deque[front]];
			begin=deque[front]+1;
			end=i;
			
		}
		
		while(front<=back &&	S[deque[back]]>S[i] )
			--back;
		deque[++back]=i;
	}
	
	g<<Max<<" "<<begin<<" "<<end-begin+1<<"\n";
	return 0;
}