Cod sursa(job #1547562)

Utilizator krityxAdrian Buzea krityx Data 9 decembrie 2015 17:28:41
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <deque>
using namespace std;

int main()
{
	int N, i, x, y, v[200001], startIndex = 1, s = 0, smax = 0, startPosition = 0, length = 0;
	deque<int> dq;
	ifstream f("buline.in");
	f >> N;
	for (i = 0; i < N; i++)
	{
		f >> x >> y;

		v[i] = y == 1 ? x : -x;
	}
	f.close();
	for (i = 0; i < N - 1; i++)
	{
		v[i + N] = v[i];
	}
	startIndex = 0;

	for (i = 0; i < 2 * N - 1; i++)
	{
		if (dq.size() == N)
		{
			dq.pop_front();
			s -= dq.front();
			startIndex++;
		}
		dq.push_back(v[i]);
		s += v[i];
		if (s < 0)
		{
			s = 0;
			dq.clear();
			startIndex = i + 1;
			continue;
			
		}
		if (s > smax)
		{
			smax = s;
			startPosition = startIndex;
			length = i - startIndex + 1;
		}
	}

	ofstream g("buline.out");
	g << smax << " " << startPosition + 1 << " " << length;
	g.close();
	return 0;
}