Cod sursa(job #2264473)

Utilizator TyFrostbyteIon Robert-Gabriel TyFrostbyte Data 20 octombrie 2018 09:48:09
Problema Deque Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <deque>
#include <algorithm>

using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
deque< pair<long long, int> > DQ;

int main() {
	int n, k;
	fin >> n >> k;

	for(int i = 0; i < k - 1; i++)
	{
		long long x;
		fin >> x;
		DQ.push_back({x, i});
	}

	long long sum = 0;
	
	for (int i = k - 1; i < n; i++) {
		while (i - DQ.front().second + 1 > k) DQ.pop_front();

		long long x;
		fin >> x;

		while (!DQ.empty() && DQ.front().first > x)
			DQ.pop_front();
		DQ.push_back({ x,i });

		sum += DQ.front().first;
	}
	fout << sum << '\n';

	return 0;
}