Cod sursa(job #1538755)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 29 noiembrie 2015 18:40:06
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <deque>

#define NMax 5000010
#define INF 10000010

using namespace std;

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

int num, len, val, vals[NMax];
long long sMin;
deque<int> dequeMin;

int main()
{
	f >> num >> len;

	for (int i = 1; i <= num; i++) {
		f >> vals[i];

		while (!dequeMin.empty() && vals[dequeMin.back()] >= vals[i])
			dequeMin.pop_back();
		dequeMin.push_back(i);

		if (i - len >= dequeMin.front())
			dequeMin.pop_front();

		if (dequeMin.back() >= len)
			sMin += vals[dequeMin.front()];
	}

	g << sMin;

	return 0;
}