Cod sursa(job #2653649)

Utilizator raikadoCri Lu raikado Data 28 septembrie 2020 18:38:42
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.52 kb
#include <fstream>
#include <iostream>
#include <utility>
#include <deque>

using namespace std;

int main(int argc, char const *argv[])
{
	ifstream fin("deque.in");
	ofstream fout("deque.out");

	int N, K;
	fin >> N >> K;

	deque<pair<int,int>> D;

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

		while (!D.empty() && D.back().first >= x)
			D.pop_back();

		D.push_back(make_pair(x, i));

		if (D.front().second <= i-K)
			D.pop_front();

		if (i >= K-1)
			sum += D.front().first;		
	}

	fout << sum;

	return 0;
}