Cod sursa(job #3000361)

Utilizator marius004scarlat marius marius004 Data 12 martie 2023 13:02:06
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
	#define inputStream cin
	#define outputStream cout
#else
	#define INPUT_PATH "deque.in"
	#define OUTPUT_PATH "deque.out"

	ifstream inputStream(INPUT_PATH);
	ofstream outputStream(OUTPUT_PATH);
#endif

int main() {
	int n, k, value;
	inputStream >> n >> k >> value;

	deque<pair<int, int>> dq;
	int answer = 0;

	dq.push_back(make_pair(value, 1));
	for (int i = 2; i <= n; ++i) {
		int value; 
		inputStream >> value;
		
		while (!dq.empty() && value <= dq.back().first)
			dq.pop_back();

		dq.push_back(make_pair(value, i));

		while(!dq.empty() && i - dq.front().second >= k)
			dq.pop_front();

		if (i >= k)
			answer += dq.front().first;
	}

	outputStream << answer;

#ifdef ONLINE_JUDGE
	inputStream.close();
	outputStream.close();
#endif

	return 0;
}