Cod sursa(job #2518703)

Utilizator mihai2003LLL LLL mihai2003 Data 6 ianuarie 2020 14:03:40
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.52 kb
#include <fstream>
#include <deque>
#include <iostream>

std::ifstream in("deque.in");
std::ofstream out("deque.out");

std::deque<std::pair<int64_t,int32_t> >d;
#define  val first
#define  ind second

int main(){
	int64_t n,k,suma=0,aux;
	in>>n>>k;
	for(int32_t i=1;i<=n;i++){
		in>>aux;
		std::pair<int64_t,int32_t>c=std::make_pair(aux,i);
		while(!d.empty() && d.front().val>aux)
			d.pop_front();
		while(!d.empty() && d.back().ind<i-k+1)
			d.pop_back();
		d.push_front(c);
		if(i>=k)
			suma+=d.back().val;
	}
	out<<suma;
}