Cod sursa(job #3001011)

Utilizator sebimihMihalache Sebastian sebimih Data 13 martie 2023 09:51:04
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <deque>

#define ll long long

using namespace std;

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

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

	deque<pair<int, int>> lista;		// nr, pozitie

	ll suma = 0;
	for (int i = 0; i < n; i++)
	{
		int x;
		fin >> x;

		// elimina nr din lista >= x
		while (!lista.empty() && x <= lista.back().first)
		{
			lista.pop_back();
		}

		// adauga nr citit
		lista.push_back(make_pair(x, i));

		// elimina nr care nu fac parte din secventa
		while (!lista.empty() && lista.front().second <= i - k)
		{
			lista.pop_front();
		}

		if (i >= k - 1)
		{
			suma += lista.front().first;
		}
	}

	fout << suma;
}

/*

	9 3

	-7
	9
	2
	4
	-1
	5
	6
	7
	1

	 0  1  2  3   4  5  6  7  8
	-7  9  2  4  -1  5  6  7  1

	* -7  9  2	-> -7
	*  9  2  4	->  2
	*  2  4 -1	-> -1
	*  4 -1  5	-> -1
	* -1  5  6	-> -1
	*  5  6  7	->  5
	*  6  7  1	->  1

*/