Cod sursa(job #2041119)

Utilizator Tyler_BMNIon Robert Gabriel Tyler_BMN Data 16 octombrie 2017 21:07:42
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <fstream>
#include <deque>
#include <vector>
#define ll long long

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

deque<int> dq;
vector<ll> sir;
int n, k;
ll s;

int main() {
	fin >> n >> k;
	for (int i = 0; i < k; i++) {
		ll x;
		fin >> x;
		sir.push_back(x);
	}

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

		if (dq.front() == i - k)
			dq.pop_front();

		if (i >= k)
			s += sir[dq.front()];
	}

	fout << s;

	return 0;
}