Cod sursa(job #724453)

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

using namespace std;

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

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

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

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

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

	return 0;
}