Cod sursa(job #632673)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 11 noiembrie 2011 23:27:54
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<cstdio>
#include<deque>
using namespace std;
FILE *in = fopen("deque.in", "r"), *out = fopen("deque.out", "w");

deque <int> lista, indice;
int n, k;
long long s;

int main(){
	fscanf (in, "%d %d", &n, &k);
	int i, x;
	for (i = 1; i <= n; i++){
		fscanf(in, "%d", &x);
		while (!lista.empty() && x <= lista.back()) {lista.pop_back(); indice.pop_back();}
		lista.push_back(x);
		indice.push_back(i);
		if (indice.front() <= i - k) {lista.pop_front(); indice.pop_front();}
		if (i >= k) s += lista.front();
	}
	
	fprintf(out, "%lld", s);
	return 0;
}