Cod sursa(job #724455)

Utilizator valiro21Valentin Rosca valiro21 Data 26 martie 2012 16:07:07
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <cstdio>
#include <list>
#define val first
#define index second

using namespace std;

list< pair<long long,int> > q;
long long n,k,tot,x;

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

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

	for(long o=1;o<=n;o++) {
		scanf("%lld",&x);
		while(!q.empty() && q.back().val>=x)
			q.pop_back();
		while(!q.empty() && q.front().index<=o-k)
			q.pop_front();
		q.push_back( make_pair(x,o) );
		if(k<=o)
			tot+=q.front().val;
	}

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

	return 0;
}