Cod sursa(job #2716360)

Utilizator Titus_Teodor_PirsanTitus-Teodor Pirsan Titus_Teodor_Pirsan Data 5 martie 2021 09:12:55
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb

#include <fstream>
#include <deque>

using namespace std;

ifstream cin("deque.in");
ofstream cout("deque.out");

deque<int> dq;
int n, k, sum;

int main()
{
	cin >> n >> k;
	int* v = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	cin.close();
	for (int i = 0; i < n; i++)
	{
		if (!dq.empty() && dq.front() == i - k)
		{
			dq.pop_front();
		}
		while (!dq.empty() && v[i] <= v[dq.back()])
		{
			dq.pop_back();
		}
		dq.push_back(i);
		if (i >= k - 1)
		{
			sum += v[dq.front()];
		}
	}
	cout << sum;
	cout.close();
	return 0;
}