Cod sursa(job #2200324)

Utilizator emiemiEmi Necula emiemi Data 30 aprilie 2018 23:46:24
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");

int main() {
	int n, k, x, i;
	pair<int, int> a;
	deque<pair<int, int> > q;
	f >> n >> k;

	int sum = 0;
	for (i = 1; i <= n; ++i) {
		f >> x;
		while (!q.empty()) {
			a = q.back();
			if (a.first > x)
				q.pop_back();
			else
				break;
		}
		q.push_back(make_pair(x, i));
		a = q.front();
		if (i - a.second >= k) {
			q.pop_front();
		}

		if (i >= k) {
			a = q.front();
			sum += a.first;
		}
	}

	g << sum << '\n';

	return 0;
}