Cod sursa(job #425312)

Utilizator titusuTitus C titusu Data 25 martie 2010 17:23:19
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
using namespace std;
#include <fstream>

int v[400004],n,m;

int main(){
	ifstream fin("buline.in"); ofstream fout("buline.out");
	fin>>n;
	int semn;
	for(int i=1;i<=n; ++i ){
		fin>>v[i]>>semn;
		if(semn==0)
			v[i]=-v[i];
	}
	
	for(int i=1;i<n;++i)
		v[i+n]=v[i];
	m=n, n=2*m-1;
	int s=v[1],start,stop,smax=v[1],index=1;
	for(int i=2;i<=n;++i){
		if(s<0)
			s=v[i], index=i;
		else{
			s+=v[i];
			if(i-index>m)
				s-=v[index++];
						
		}
		if(s>smax)
			smax=s, start=index, stop=i;
	}
	fout<<smax<<" "<<start<<" "<<stop-start+1<<endl;
	return 0;
}