Cod sursa(job #2646875)

Utilizator IRadu1529Radu Ionescu IRadu1529 Data 2 septembrie 2020 12:12:07
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <deque>
#include <vector>
#include <fstream>

using namespace std;

ifstream fin("deque.in");
ofstream fout("deque.out");

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

	fin >> n >> k;

	deque<int> d;
	vector<int> v(n + 1);

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

	d.push_back(1);

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

		d.push_back(i);
	}

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

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

		d.push_back(i);

		if (d.front() <= i - k)
			d.pop_front();

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

	}

	fout << s;
}