Cod sursa(job #2680165)

Utilizator davidcotigacotiga david davidcotiga Data 2 decembrie 2020 20:21:17
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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


int main() {

	int N, K;
	deque<int> v;
	deque<int> ind;

	fin >> N >> K;

	int nr;
	long long rez = 0;


	for (int i = 0; i < N; ++i) {
		fin >> nr;

		while (!v.empty()) {
			if (v.back() >= nr) {
				v.pop_back();
				ind.pop_back();
			}
			else
				break;
		}

		v.push_back(nr);
		ind.push_back(i);

		if (!ind.empty())
			while (i - ind.front() >= K && !ind.empty()) {
				ind.pop_front();
				v.pop_front();
			}

		if (i >= K - 1 && !v.empty()) {
			rez += v.front();
		}
	}

	fout << rez;

	return 0;
}