Cod sursa(job #2293809)

Utilizator DawlauAndrei Blahovici Dawlau Data 1 decembrie 2018 16:47:10
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <vector>
#include <deque>
#include <climits>
#include <cmath>
#include <algorithm>

using namespace std;

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

const int Inf = INT_MAX;

class DequeItm {

	public:
		int sum, idx;
};

int main() {

	int N;
	fin >> N;

	vector <int> Arr(2 * N + 1);
	for (int idx = 1; idx <= N; ++idx) {

		int val;
		bool type;
		fin >> val >> type;

		if (type == 0)
			Arr[idx] = Arr[idx + N] = -val;
		else
			Arr[idx] = Arr[idx + N] = val;
	}

	int S = -Inf, P = 0, L = 0;

	deque <DequeItm> Deque;
	Deque.push_back({ 0, 0 });

	int partSum = 0;
	for (int idx = 1; idx <= 2 * N; ++idx) {

		while (!Deque.empty() && Deque.front().idx < idx - N + 1)
			Deque.pop_front();

		partSum += Arr[idx];
		int sum = partSum - Deque.front().sum;

		if (sum > S) {

			S = sum;
			P = Deque.front().idx;
			L = idx - Deque.front().idx;
		}
		else if (sum == S) {

			if (Deque.front().idx < P) {

				P = Deque.front().idx;
				L = idx - Deque.front().idx;
			}
			else if (Deque.front().idx == P)
				if (idx - Deque.front().idx < L)
					L = idx - Deque.front().idx;
		}

		while (!Deque.empty() && partSum < Deque.back().sum)
			Deque.pop_back();
		Deque.push_back({partSum, idx});
	}

	fout << S << ' ' << P + 1 << ' ' << L;
}