Cod sursa(job #2069596)

Utilizator FipNadCeara Filip FipNad Data 18 noiembrie 2017 16:40:05
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

deque<int>coada;
int n, v[400010], i, r1, pozitie, lungime, x;

int main()
{
	f >> n;
	for (i = 1; i <= n; i++) {
		f >> v[i] >> x;
		if (x == 0)v[i] = v[i] * -1;
		v[i + n] = v[i];
	}
	for (i = 1; i <= 2 * n; i++)v[i] = v[i] + v[i - 1];
	for (i = 1; i <= n; i++) {
		while (coada.size() && v[coada.back()] > v[i])
			coada.pop_back();
		coada.push_back(i);

		if (coada.front() == i - n)
			coada.pop_front();

		if (v[i] - v[coada.front()] > r1) {
			r1 = v[i] - v[coada.front()];
			pozitie = coada.front() + 1;
			lungime = i - pozitie + 1;
		}

	}

	g << r1+1 << " " << pozitie << " " << lungime;
	//for (i = 1; i <= 2 * n; i++)g << v[i]<<" ";

	f.close();
	g.close();
    return 0;
}