Cod sursa(job #800205)

Utilizator gabriela95Andreea Gabriela gabriela95 Data 20 octombrie 2012 21:47:46
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int v[200001],d[200001],i,j,n,a,p,nr, smax, s1min, pmax, lmax, lung, pfmax, lc, pc, lungmax, S;
int main()
{
	f>>n;
	for(i=1;i<=n;i++)
	{
	f>>v[i]>>a;
	if(a==0) {
		v[i]=-v[i];
		}
	S += v[i];
	}
	d[1]=v[1];
	smax = d[1];
	pmax = 1;
	lmax = 1;
	for (i=2;i<=n;i++){
		if (v[i] > d[i-1] + v[i]) {
			d[i] = v[i];
			pc = i;
			lc = 1;
		} else {
			d[i] = d[i-1] + v[i];
			lc ++;
		}
		if (d[i] > smax) {
			smax = d[i];
			pmax = pc;
			lmax = lc;
		}
	}
	d[1] = v[1];
	s1min = d[1];
	for(i=2;i<=n;i++) {
		if (d[i-1] + v[i] < v[i]) {
			d[i] = d[i-1] + v[i];
			lung ++;
		} else {
			d[i] = v[i];
			lung = 1;
		}
		if (d[i] <= s1min) {
			s1min = d[i];
			pfmax = i;
			lungmax = lung;
		}
	}
	s1min = S - s1min;
	if (s1min > smax) {
		smax = s1min;
		pmax = pfmax+1;
		lmax = n-lungmax;
	}
	g<<smax<<" "<<pmax<<" "<<lmax;
return 0;
}