Cod sursa(job #425961)

Utilizator slayer4uVictor Popescu slayer4u Data 26 martie 2010 12:10:10
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <cstdio>
#include <deque>
using namespace std;

deque <pair <int, int> > q;

long n, k, x;
long long rez;

void add(long x, long i)
{
	while (q.size() && x < q.back().first)
		q.pop_back();
	q.push_back(make_pair(x, i));
}

int main()
{
	freopen ("deque.in", "rt", stdin);
	freopen ("deque.out", "wt", stdout);

	scanf("%ld %ld", &n, &k);

	for (long i = 0; i < k - 1; ++i)
	{
		scanf("%ld", &x);
		add(x, i);
	}

	for (long i = k - 1; i < n; ++i)
	{
		scanf("%ld", &x);
		add(x, i);
		
		if (i - q.front().second >= k)
			q.pop_front();

		rez += q.front().first;
	}

	printf("%lld\n", rez);

	return 0;
}