Cod sursa(job #2230975)

Utilizator TrixerAdrian Dinu Trixer Data 12 august 2018 16:08:18
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <utility>

using namespace std;

int main()
{
	int n, k, x;
	int sum = 0;
	deque<pair<int, int>> d;

	ifstream fin("deque.in");
	fin >> n >> k;
	for (int i = 0; i < n; i++) {
		fin >> x;
		while (not d.empty() and d.back().first >= x)
			d.pop_back();
		d.push_back({x, i});

		if (i >= k - 1) {
			if (d.front().second <= i - k)
				d.pop_front();

			sum += d.front().first;
		}
	}
	fin.close();

	ofstream fout("deque.out");
	fout << sum;
	fout.close();

	return 0;
}