Cod sursa(job #2264458)

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

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

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

	for(int i = 0; i < k - 1; i++)
	{
		int x;
		fin >> x;
		DQ.push_back({x, i});
	}
	
	for (int i = k - 1; i < n; i++) {
		while (i - DQ.front().second + 1 > k) DQ.pop_front();

		int x;
		fin >> x;

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

		minimums.push_back(DQ.front().first);
	}

	int sum = 0;
	for (int n : minimums) sum += n;
	fout << sum << '\n';

	return 0;
}