Cod sursa(job #1480508)

Utilizator aimrdlAndrei mrdl aimrdl Data 2 septembrie 2015 18:06:22
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <deque>
 
using namespace std;

int main (void) {
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);
	
	int n, k;
	scanf("%d %d", &n, &k);
	
	pair <int, int> temp;
	
	deque < pair <int, int> > dq;
	
	int s = 0;
	scanf("%d", &temp.first);
	temp.second = 1;
	
	dq.push_front(temp);
	
	
	for (int i = 2; i <= n; ++i) {
		++temp.second;
		
		if (i - dq.front().second >= k) dq.pop_front();
		
		scanf("%d", &temp.first);
		
		while (dq.size() > 1 && dq.back().first >= temp.first) {
			dq.pop_back();
		}
		if (dq.front().first > temp.first) dq.pop_front();
		
		dq.push_back(temp);
		
		if (i >= k) s += dq.front().first;
	}
	
	printf("%d", s);
	
	return 0;
}