Cod sursa(job #547484)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 6 martie 2011 13:18:12
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
/*
	Elem noi sterg din coada de la sfarsit cele mai mari ca ea.
    (sunt preferate elem minime de indice mai mare)
*/

#include <cstdio>
#include <deque>
using namespace std;

const int N = 5000001;

deque<int> coada;
int v[N];
int n,k;

void citire()
{
	scanf("%d%d",&n,&k);
	for (int i = 1; i <= n; ++i)
		scanf("%d",&v[i]);
}

void rezolvare_deque()
{
	long long s=0;
	for (int i = 1; i <= n; ++i)
	{
		while (!coada.empty() && v[i] <= v[coada.back()])
			coada.pop_back();
		coada.push_back(i);
		if (coada.front() == i-k)
			coada.pop_front();
		if (i >= k)
			s += v[coada.front()];
	}
	printf("%lld",s);
}

int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	citire();
	rezolvare_deque();
	return 0;
}