Cod sursa(job #633262)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 13 noiembrie 2011 13:51:44
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <deque>

using namespace std;

long n, k, i, a, sum;

deque < pair < long, long > > dq;

int main() {
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);
	
	scanf("%ld %ld", &n, &k);
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &a);
		if (i > 1)
			while (dq[dq.size() - 1].first >= a) 
				dq.pop_back();
		
		dq.push_back(make_pair(a, i));
		
		if (dq[0].second <= i - k) 
			dq.pop_front();
		
		if (i >= k)
			sum += dq[0].first;
	}
	
	printf("%ld\n", sum);
	
	return 0;
}