Cod sursa(job #236359)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 27 decembrie 2008 12:00:23
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <deque>
#include <vector>
using namespace std;

int	N,K,S,x,i;
deque<int> D;
vector<int> A;

void push() {
	while ( !D.empty() && A[i] < A[D.back()] ) D.pop_back();
	D.push_back(i);
}

void pop() {
	while ( i-D.front()+1 > K ) 
		D.pop_front();
}

void debug() {
	deque<int>::iterator it;
	for ( it=D.begin(); it!=D.end(); ++it )
		fprintf(stderr, "%4d(%2d) ", A[*it],*it);
	fprintf(stderr, "\n");
}

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

	scanf("%d %d", &N, &K);
	A.resize( N );
	for ( i=0; i<K-1; ++i ) {
		scanf("%d", &x);
		A[i] = x;
		push();
//		fprintf(stderr, "IN  : ");debug();
	}
	for ( ; i<N; ++i ) {
		scanf("%d", &x);
		A[i] = x;

		push();
//		fprintf(stderr, "IN  : ");debug();
		pop();
//		fprintf(stderr, "OUT : ");debug();

		S += A[D.front()];
	}

	printf("%d\n", S);
	return 0;
}