Cod sursa(job #832271)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 10 decembrie 2012 11:06:49
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int N=200100;

int v[2*N],n;

int main(){
	int i,x,y;
	in>>n;
	for(i=0;i<n;++i){
		in>>x>>y;
		if(!y){
			x=-x;
		}
		v[i]=v[n+i]=x;
	}
	deque<int> dq;
	int s=0,smax=-N,poz=0,nr=0;
	for(i=0;i<2*n;++i){
		dq.push_back(v[i]);
		s+=v[i];
		if(s>smax){
			smax=s;
			poz=i%n + 1;
			nr=dq.size();
		}
		if(dq.size()==n){
			s-=dq.front();
			dq.pop_front();
		}
		while(s<0 && dq.size()){
			s-=dq.front();
			dq.pop_front();
		}
	}
	poz-=nr;
	poz++;
	if(poz<=0){
		poz+=n;
	}
	out<<smax<<" "<<poz<<" "<<nr;
}