Cod sursa(job #3356416)

Utilizator lefterache_stefanLefterache Stefan lefterache_stefan Data 31 mai 2026 18:51:24
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.54 kb
#include <deque>
#include <fstream>
#include <vector>
using namespace std;

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

int main() {
	int n, k;
	fin >> n >> k;

	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) {
		fin >> a[i];
	}

	deque<int> dq;
	long long suma_minime = 0;

	for (int i = 1; i <= n; i++) {
		while (!dq.empty() && a[dq.back()] >= a[i]) {
			dq.pop_back();
		}
		dq.push_back(i);

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

		if (i >= k) {
			suma_minime += a[dq.front()];
		}
	}

	fout << suma_minime << '\n';
}