Cod sursa(job #1060776)

Utilizator PokerDawgCristian Popov PokerDawg Data 18 decembrie 2013 18:11:42
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <fstream>
#include <deque>

using namespace std;

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

long int n, k, x, s = 0;
deque <int> v, d;

int main()
{
	in >> n >> k;
	for (int i = 1; i <= n; i ++)
	{
		in >> x;
		v.push_back(x);
	}

	for (int i = 0; i < n; i ++)
	{
		while (!d.empty() && v[i] < v[d.back()])
			d.pop_back();
		while (!d.empty() && d.front() <= i - k)
			d.pop_front();
		d.push_back(i);

		if (i >= k - 1)
			s += v[d.front()];
	}

    out << s;

    in.close();
    out.close();
    return 0;
}