Cod sursa(job #1420563)

Utilizator razvan3895Razvan-Mihai Chitu razvan3895 Data 18 aprilie 2015 18:22:03
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <stdio.h>
#include <deque>

using namespace std;

struct elem{
	int val;
	int poz;
};

int main() {
	deque<elem> dq;
	int n, k, sum = 0;
	elem a;
	scanf("%d%d", &n, &k);
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);

	for(int i = 0; i < k - 1; ++i) {
		scanf("%d", &a.val);
		a.poz = i;
		while(!dq.empty() && a.val < dq.back().val)
			dq.pop_back();
		dq.push_back(a);
	}

	for(int i = k - 1; i < n; ++i) {
		if(i - dq.front().poz >= k)
			dq.pop_front();

		scanf("%d\n", &a.val);

		a.poz = i;

		while(!dq.empty() && a.val < dq.back().val) {
			dq.pop_back();		
		}
		dq.push_back(a);
		
		sum += dq.front().val;
	}

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