Cod sursa(job #2887417)

Utilizator simaderalSimader Albert simaderal Data 9 aprilie 2022 16:22:11
Problema Deque Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <stack>
#include <fstream>
#include <string>
#include <cstring>
#include <deque>
using namespace std;
//#pragma warning(disable : 4996)
ifstream in("deque.in");
ofstream out("deque.out");

//deque<int> d;
//int a[10000],
//n,
//k,
//s = 0;
//
//in >> n >> k;
//for (int i = 1; i <= n; ++i) {
//	in >> a[i];
//	while (d.size() && a[d.back()] > a[i]) {
//		d.pop_back();
//	}
//	d.push_back(i);
//	if (d.front() == i - k) d.pop_front();
//	if (i >= k) s += a[d.front()], cout << a[d.front()] << " ";
//}
//out << s;

int main(void) {
	int d[1000];
	int a[1000],
		n,
		k,
		s = 0,
		front = 1,
		back = 0;
	in >> n >> k;
	for (int i = 1; i <= n; i++) {
		in >> a[i];
		while (front <= back && a[i] <= a[d[back]]) back--;
		d[++back] = i;
		if (d[front] == i - k) front++;
		if (i >= k) s += a[d[front]];
	}
	out << s;
}