Cod sursa(job #503400)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 22 noiembrie 2010 20:28:32
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>

using namespace std;

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

int n,v[1<<19],st=0;

void prelucrare(){
	int i,j,sc=0,smax=0,smin=0,p=0,l=0,pmax1,lmax1,pmax2,lmax2;
	for(i=1;i<=n;i++){
		sc+=v[i];
		if(sc<=0){
			sc=0;
			p=i;
			l=0;
		}
		else{
			l++;
			if(sc>smax){
				smax=sc;
				pmax1=p;
				lmax1=l;
			}
		}
	}
	sc=0;
	for(i=1;i<=n;i++){
		if(sc>=0){
			sc=0;
			p=i;
			l=0;
		}
		sc+=v[i];
		++l;
		if(sc<smin){
			smin=sc;
			pmax2=p;
			lmax2=l;
		}
	}
	if(smax>st-smin){
		out<<smax<<"\n"<<pmax1<<lmax1;
		return;
	}
	out<<st-smin<<"\n"<<pmax2+lmax2<<"\n"<<n-lmax2;
}

int main(){
	int i,x,y;
	in>>n;
	for(i=1;i<=n;i++){
		in>>x>>y;
		if(y==0)
			v[i]=x*(-1);
		else
			v[i]=x;
		st+=v[i];
	}
	prelucrare();
	return 0;
}