Cod sursa(job #799967)

Utilizator mariamFiciu Maria mariam Data 20 octombrie 2012 15:04:12
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
using namespace std;
int v[200001],d[200001],i,j,n,a,p,nr, smax, s1min, pmax, lmax, lung, pfmax, lc, pc, lungmax, S;

int main()
{
	ifstream f("buline.in");
	ofstream g("buline.out");
	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;
		}
	}
	//calculez subsecventa de suma minim care se termina cat mai devreme
	
	
	
	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;
}