Cod sursa(job #673466)

Utilizator ukiandreaAndreea Lucau ukiandrea Data 4 februarie 2012 15:30:14
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <stdio.h>
#include <stdint.h>

#include <deque>

int main()
{
	int n, k;
	std::deque<std::pair<int64_t, int64_t> > deq;

	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);

	scanf("%d %d\n", &n, &k);

	int64_t s = 0;
	for (int i = 1; i <= n; i++) {
		int64_t x;
		scanf("%lld\n", &x);

		while (deq.size () && deq.back().first >= x) 
			deq.pop_back();
		
		deq.push_back(std::pair<int64_t, int64_t>(x, i));

		if (i >= k) {
			if (deq.front().second < (i - k + 1))
				deq.pop_front();
			s += deq.front().first;
		}
	}

	printf("%lld\n", s);
	return 0;
}