Cod sursa(job #2038823)

Utilizator robuvedVictor Robu robuved Data 13 octombrie 2017 23:59:33
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.49 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream in("deque.in");
ofstream out("deque.out");

int main()
{
	int N, K;
	in >> N >> K;
	long long sum = 0;
	deque<pair<int, int>> d;
	for (int i = 0; i < N; i++)
	{
		int x;
		in >> x;
		while (!d.empty() && (d.back().first > x))
		{
			d.pop_back();
		}
		d.push_back({ x, i });
		if (d.front().second <= i - K)
		{
			d.pop_front();
		}
		if (i >= K - 1)
		{
			sum += d.front().first;
		}
	}
	out << sum;
}