Cod sursa(job #633265)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 13 noiembrie 2011 13:56:02
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 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);
		while (dq.size() > 0 && dq.back().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;
}