Cod sursa(job #2833068)

Utilizator SuyggyuDumitriu Florin Suyggyu Data 14 ianuarie 2022 17:56:19
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
/// https://www.infoarena.ro/problema/deque
#include <fstream>
#include <deque>

using namespace std;

int main()
{
	ifstream fin("deque.in");
	ofstream fout("deque.out");
	deque<int> dq;
	int n, k, suma = 0;
	fin >> n >> k;
	int numere[n];
	
	for(int i = 0; i < n; fin >> numere[i++]);

	for(int i = 0; i < n; i++)
	{
		while(!dq.empty() && numere[dq.back()] >= numere[i])
			dq.pop_back();

		dq.push_back(i);

		if(dq.back()-dq.front()+1 > k)
			dq.pop_front();

		if(i >= k-1)
			suma += numere[dq.front()];
	}

	fout << suma << endl;

	return 0;
}