Cod sursa(job #425387)

Utilizator titusuTitus C titusu Data 25 martie 2010 18:24:24
Problema Buline Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 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;
	int s=v[1],start=1,stop=1,smax=v[1],index=1;
	for(int i=2;i<=n;++i){
		if(s<0)
			s=v[i], index=i;
		else{
			s += v[i];
			while(i-index+1>m)
				s -= v[ index++ ];
			while(v[index]<0)
				s -= v[index++];
		}
		if(s > smax)
			smax = s, start = index, stop = i;
	}
	fout<<smax<<" "<<start<<" "<<stop - start + 1<<endl;
	return 0;
}