Cod sursa(job #669791)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 27 ianuarie 2012 19:29:42
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<iostream>
#include<fstream>
using namespace std;
int v[200001],s[400001],deque[400001];
int main ()
{
	int i,n,x,y,max,start,l,st,dr,m;
	ifstream f("buline.in");
	ofstream g("buline.out");
	f>>n;
	for(i=1;i<=n;i++) {
		f>>x>>y;
		if(y==0)
			x=x*(-1);
		v[i]=x;
	}
	f.close();
	for(i=1;i<=n;i++)
		s[i]=s[i-1]+v[i];
	for(i=1;i<=n;i++)
		s[i+n]=s[i+n-1]+v[i];
	m=n+n;
	st=1;
	dr=0;
	max=-1;
	for(i=1;i<=m;i++) {
		while((st<=dr)&&(s[deque[dr]]>s[i]))
			dr--;
		deque[++dr]=i;
		if((i-deque[st])==n)
			st++;
		if((s[i]-s[deque[st]])>max) {
			max=s[i]-s[deque[st]];
			start=deque[st]+1;
			l=i-deque[st];
		}
	}
	g<<max<<" "<<start<<" "<<l;
	g.close();
	return 0;
}