Cod sursa(job #632680)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 11 noiembrie 2011 23:46:29
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include<fstream>
#include<deque>
using namespace std;

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

int main(){
	ifstream fin ("deque.in");
	fin >> n >> k;
	int i, x;
	for (i = 1; i <= n; i++){
		fin >> 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();
	}
	
	ofstream fout("deque.out");
	fout << s <<"\n",	fout.close();
	return 0;
}