Cod sursa(job #2008124)

Utilizator epermesterNagy Edward epermester Data 5 august 2017 14:28:05
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include<fstream>
#include<deque>
using namespace std;

struct minimum {
	int ertek;
	int poz;
};

int main() {
	ifstream in("deque.in");
	int N, K;
	in >> N >> K;
	deque<minimum> dq;
	long long s=0;
	for (int i = 0;i < N;++i) {
		int nr;
		in >> nr;
		while (!dq.empty() && dq.back().ertek >= nr)
			dq.pop_back();
		minimum temp { nr, i };
		dq.push_back(temp);
		if (i - dq.front().poz == K)
			dq.pop_front();
		if(i>=K-1) s += dq.front().ertek;
	}
	ofstream out("deque.out");
	out << s;
}