Cod sursa(job #1717768)

Utilizator TwoOfDiamondsDaniel Alexandru Radu TwoOfDiamonds Data 15 iunie 2016 19:02:06
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <deque>>

using namespace std;

struct punct
{
	int val;
	int poz;
};

int main()
{
	fstream in("deque.in");
	ofstream out("deque.out");

	deque<punct> coada;
	int sum = 0;
	int n, k; in >> n >> k;

	for (int i = 1; i <= n; i++)
	{
		int x; in >> x;
		punct p; p.poz = i; p.val = x;

		while (!coada.empty() && x <= coada.back().val) coada.pop_back();

		coada.push_back(p);

		if (coada.front().poz == i - k) coada.pop_front();

		if (i >= k)
			sum += coada.front().val;

	}

	out << sum << endl;
	return 0;

}