Cod sursa(job #1401317)

Utilizator ancabdBadiu Anca ancabd Data 25 martie 2015 19:44:09
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <deque>

using namespace std;

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

deque<int> d;
int main()
{
    int n;
    int v[400001], beg, f;
    int s = -100000;

	fin >> n;

	int x1, x2;

	for (int i = 1; i <= n; ++i)
	{
		fin >> x1 >> x2;
		if (x2 == 0)v[i] = x1 * -1;
		else v[i]= x1;
	}

	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 (s <v[i] -v[d.front()])
		{
			s = v[i] - v[d.front()];
			f = i - d.front();
			beg = d.front()+ 1;
		}
	}

	fout << s << ' ' << beg << ' ' << f;
}