Cod sursa(job #1460652)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 13 iulie 2015 14:07:14
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <deque>
using namespace std;

int main() {
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);
	deque< pair<int, int> > D;
	int N, K;
	scanf("%d%d", &N, &K);
	int s = 0;
	for (int i = 1; i <= N; i++) {
		int elem;
		scanf("%d", &elem);
		while (!D.empty() && D.back().first > elem)
			D.pop_back();
		D.push_back({ elem, i });
		if (D.front().second <= i - K)
			D.pop_front();
		if (i >= K)
			s += D.front().first;
	}
	printf("%d\n", s);
	return 0;
}