Cod sursa(job #1603162)

Utilizator krityxAdrian Buzea krityx Data 17 februarie 2016 11:29:41
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <deque>
#include <algorithm>
#define NMAX 400001
using namespace std;

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

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

	dq.push_back(1);
	for (i = 2; i <= 2 * N - 1; i++)
	{
		if (dq.size() > N)
		{
			dq.pop_front();
		}
		if (partialSums[i] - partialSums[dq.front()] > smax)
		{
			smax = partialSums[i] - partialSums[dq.front()];
			startIndex = dq.front() + 1;
			length = i - dq.front();
		}
		while (!dq.empty() && partialSums[i] < partialSums[dq.back()])
		{
			dq.pop_back();
		}
		dq.push_back(i);
	}
	ofstream g("buline.out");
	g << smax << " " << startIndex << " " << length;
	g.close();
	return 0;
}