Cod sursa(job #3210943)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 7 martie 2024 19:28:50
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>

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

using ll = long long;
using ull = unsigned long long;

struct cv {
	int poz;
	ll val; 
};

int n,k;
ll ans;
deque<cv> dq;
int main() {
	fin >> n >> k;
	for (int i = 1; i <= n; i++) {
		ll rd;
		fin >> rd;
		while (!dq.empty() && dq.back().val > rd) {
			dq.pop_back();
		}
		dq.push_back({i,rd});
		while (!dq.empty() && dq.front().poz == i - k) {
			dq.pop_front();
		}
		if (i >= k && n >= i)
			ans += dq.front().val;
	}
	fout << ans;
	return 0;
}