Cod sursa(job #2649222)

Utilizator IRadu1529Radu Ionescu IRadu1529 Data 13 septembrie 2020 16:48:15
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <vector>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");

int main()
{
	int n, k;
	long long int s = 0;

	fin >> n >> k;

	vector<int> v(n);

	deque<int> d;

	for (int i = 0; i < n; i++)
		fin >> v[i];

	for (int i = 0; i < k; i++)
	{
		while (!d.empty() && v[d.back()] > v[i])
			d.pop_back();

		d.push_back(i);
	}

	s += v[d.front()];

	for (int i = k; i < n; i++)
	{
		while (!d.empty() && v[d.back()] > v[i])
			d.pop_back();

		if (!d.empty() && i - d.front() + 1 > k)
			d.pop_front();

		d.push_back(i);

		s += v[d.front()];
	}

	fout << s;
}