Cod sursa(job #1077847)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 11 ianuarie 2014 18:37:55
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
using namespace std;

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

#define INF 1<<31
#define MAXN 200005

int N, v[MAXN];

int main()
{
	int i, tip;
	int suma = 0, s, smax, inceput, smaxincep, smaxsfarsit, _s, _smax, _inceput, _sfarsit, _smaxincep, _smaxsfarsit;

	f >> N;
	for (i = 1; i <= N; ++i)
		f >> v[i] >> tip, v[i] *= (tip == 0) ? (-1) : 1, suma += v[i];

	s = smax = _s = _smax = -INF;
	for (i = 1; i <= N; ++i)
	{
		if (s <= 0) s = 0, inceput = i;
		if (_s <= 0) _s = 0, _inceput = i;
		s += v[i];
		_s += v[i] * (-1);
		if (s > smax) { smax = s, smaxincep = inceput, smaxsfarsit = i; }
		if (_s > _smax) { _smax = _s, _smaxincep = _inceput, _smaxsfarsit = i; }
	}
	_smax = suma + _smax;
	if (_smax > smax) g << _smax << ' ' << _smaxsfarsit + 1 << ' ' << (N - _smaxsfarsit) + _smaxincep - 1 << '\n';
	else			  g << smax << ' ' << smaxincep << ' ' << smaxsfarsit << '\n';
}