Cod sursa(job #1225494)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 2 septembrie 2014 17:54:54
Problema Deque Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <deque>
#include <utility>

using namespace std;

long long n, k, elem;
long long sum;

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