Cod sursa(job #2038802)

Utilizator robuvedVictor Robu robuved Data 13 octombrie 2017 23:39:21
Problema Deque Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 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.front().second <= i - K || d.front().first > d.back().first))
		{
			d.pop_front();
		}
		d.push_back({ x, i });
		while (d.front().second <= i - K || d.front().first > x)
		{
			d.pop_front();
		}
		if (i >= K - 1)
		{
			sum += d.front().first;
		}
	}
	out << sum;
}