Cod sursa(job #2522041)

Utilizator cezar_titianuTitianu Cezar cezar_titianu Data 11 ianuarie 2020 21:36:57
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <queue>

using namespace std;

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

struct entr
{
	int val;
	int sav;
} nrf;

deque <entr> deq;

int nrnr, nrk, poz = 0, sum = 0, nri;

void push(int val, int sav)
{
	if (!deq.empty()) {
		while (deq.front().val > val)
		{
			deq.pop_front();
			if (deq.empty()) {
				break;
			}
		}
	}
	nrf.val = val;
	nrf.sav = sav;
	deq.push_front(nrf);
}

int main()
{
	fin >> nrnr >> nrk;
	for (int index = 0; index < nrk; index++)
	{
		fin >> nri;
		push(nri, index);
	}
	sum = sum += deq.back().val;
	for (int index = nrk; index < nrnr; index++)
	{
		fin >> nri;
		push(nri, index);
		if (!deq.empty()) {
			while (index - deq.back().sav >= nrk)
			{
				deq.pop_back();
				if (deq.empty()) {
					break;
				}
			}
		}
		sum += deq.back().val;
	}
	fout << sum;
}