Cod sursa(job #485312)

Utilizator darrenRares Buhai darren Data 17 septembrie 2010 21:30:44
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <deque>

using namespace std;

int n;
long long v[400000];
deque<int> d;
long long s, beg, end;

int main()
{
	ifstream fin("buline.in");
	ofstream fout("buline.out");

	fin >> n;
	for (int i = 1, x1, x2; i <= n; ++i)
	{
		fin >> x1 >> x2;
		v[i] = x1 * (x2 == 0 ? -1 : 1);
	}
	for (int i = n + 1; i < 2 * n; ++i)
		v[i] = v[i - n];
	for (int i = 1; i < 2 * n; ++i)
		v[i] += v[i - 1];

	for (int i = 1; i < 2 * n; ++i)
	{
		while (!d.empty() && d.front() <= i - n)
			d.pop_front();
		while (!d.empty() && v[d.back()] > v[i])
			d.pop_back();
		d.push_back(i);

		if (v[i] - v[d.front()] > s)
		{
			s = v[i] - v[d.front()];
			beg = d.front() + 1;
			end = i - d.front();
		}
	}

	fout << s << ' ' << beg << ' ' << end;

	fin.close();
	fout.close();
}