Cod sursa(job #2887469)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 9 aprilie 2022 18:14:26
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
#define cin f
#define cout g

int n, k;
long long sum;
deque < pair < int , int > > d;
int main()
{
	cin >> n >> k;
	int x; cin >> x;
	d.push_back(make_pair(x, 1));
	for(int i = 2; i < k; i ++)
	{
		cin >> x;
		while(! d.empty() and x < d.back().first)
			d.pop_back();
		d.push_back(make_pair(x, i));
	}
	for(int i = k; i <= n; i ++)
	{
		cin >> x;
		while(! d.empty() and x < d.back().first)
			d.pop_back();
		d.push_back(make_pair(x, i));
		sum += d.front().first;
		if(i - d.front().second + 1 >= k)
			d.pop_front();
	}
	cout << sum;
	return 0;
}