Cod sursa(job #515859)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 22 decembrie 2010 16:03:27
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

int main () {
	int sc,smax1,sss,smax2,dd,n,m,i,j,a,s,x[200001];
	ifstream aa("buline.in");
	ofstream ss("buline.out");
	aa >> n; sss=0; a=1; s=1;
	for (i=1;i<=n;++i) {
		aa >> x[i] >> dd;
		if (dd==0) x[i]=-x[i];
		sss=x[i]+sss;
	}
	smax2=200000; sc=0; smax1=-200000;
	for (i=1;i<=n;++i) {
		sc=sc+x[i];
		if (sc>smax1) {smax1=sc;
			s=i-a+1;
			j=a;
		}
		if (sc<0) {sc=0; a=i+1;}
	}
	sc = 0;
	a = 1;
	for (i=1;i<=n;++i) {
		sc=sc+x[i];
		if (sc<smax2) 
		{
			smax2=sc;
			s=i-a+1;
			j=a+s;
			s=n-s;
		}
		if (sc>0) 
		{
			sc=0; 
			a=i+1;
		}
	}
	if (sss-smax2>smax1) smax1=sss-smax2;
	ss << smax1 << " " << j << " " << s;
	ss.close();
	aa.close();
	return 0;
}