Cod sursa(job #936202)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 6 aprilie 2013 01:04:29
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <algorithm>
#include <cstdio>
#include <deque>
#include <vector>
using namespace std;

long long n, k, x[5000001], s;

deque<long long> d;

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

	scanf("%lld%lld", &n, &k);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld", &x[i]);
		while(!d.empty() &&(x[d.back()] >= x[i]))
			d.pop_back();
		d.push_back(i);
		/*
		while(i-k+1 > d.front())
			d.pop_front();
		s += x[d.front()];
		*/
		if(d.front() == i-k)
			d.pop_front();
		if(i >= k)
			s += x[d.front()];
		
	}
	printf("%lld", s);
	return 0;
}