Cod sursa(job #1225868)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 3 septembrie 2014 20:53:29
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <iostream>
#include <deque>
#include <utility>

using namespace std;

int n, k, el;
long long sum;

int main(){
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);
	scanf("%d%d", &n, &k);
	deque<pair<int, int>> dq;
	for (int i = 0; i < n; i++){
		scanf("%d", &el);
		if (i >= k){
			sum += dq.front().first;
			if (dq.front().second <= i - k){
				dq.pop_front();
			}
		}
		while (dq.size() && dq.back().first > el){
			dq.pop_back();
		}
		dq.push_back(make_pair(el, i));
	}
	sum += dq.front().first;
	cout << sum;
	return 0;
}