Cod sursa(job #672544)

Utilizator Sanduleac_VladSanduleac Vllad Alexandru Sanduleac_Vlad Data 2 februarie 2012 16:04:06
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#include <deque>
using namespace std;

long N, k, crt;
long long smin;
struct L {
	long nr, d;
};
deque<L> q;

int main() {
	long i, j;
	L tmp;
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);
	scanf("%ld %ld", &N, &k);
	scanf("%ld", &crt);
	tmp.nr = crt;
	tmp.d = 1;
	q.push_back(tmp);
	for(i = 2; i <= k; i++) {
		scanf("%ld", &crt);
		while(!q.empty() && crt <= q.back().nr) {
			q.pop_back();
		}
		tmp.nr = crt;
		tmp.d = i;
		q.push_back(tmp);
	}
	smin += q.front().nr;
	for(; i <= N; i++) {
		scanf("%ld", &crt);
		while(!q.empty() && crt <= q.back().nr) {
			q.pop_back();
		}
		tmp.nr = crt;
		tmp.d = i;
		q.push_back(tmp);
		if(q.back().d - q.front().d == k)
			q.pop_front();
		smin += q.front().nr;
	}
	printf("%ld", smin);
	return 0;
}