Cod sursa(job #1477607)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 26 august 2015 16:31:52
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <cstdio>
#include <vector>
#include <deque>

#define f first
#define s second

using namespace std;

deque < pair <int, int> > D;
int N, K, X; long long S;

int main(){

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

	scanf("%d %d", &N, &K);

	for(int i = 1; i <= N; i ++){
		scanf("%d", &X);

		while(!D.empty() && D.back().s >= X)
			D.pop_back();
		D.push_back( make_pair(i, X) );

		if(i - D.front().f == K)
			D.pop_front();

		if(i >= K)
			S += D.front().s;
	}

	printf("%lld", S);

	fclose(stdin );
	fclose(stdout);

	return 0;
}