Cod sursa(job #708441)

Utilizator andrey932Andrei andrey932 Data 6 martie 2012 20:12:21
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");

struct nod {
	int val;
	int poz;
};

deque<nod> deq;
nod aux;
int i,n,k,a;
long long rez;

int main() {
	fin>>n>>k;
	for(i=1;i<=n;i++) {
		fin>>a;
		while ( (!deq.empty()) && (deq.back().val>a) ) deq.pop_back();
		aux.val=a;
		aux.poz=i;
		deq.push_back(aux);
		if (i>=k) {
			while ( deq.front().poz<=i-k ) deq.pop_front();
			rez+=deq.front().val;
		}		
	}
	fout<<rez<<"\n";
	cout<<rez;
	fout.close();
}