Cod sursa(job #604572)

Utilizator sergiupPopescu Sergiu sergiup Data 23 iulie 2011 15:24:08
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <deque>

using namespace std;

deque<int> q;
int sir[5000005];

int main()
{
	int n,k;

	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);

	scanf("%d%d",&n,&k);

	for (int i = 0 ; i < n ; ++i)
	{
		scanf("%d",&sir[i]);
	}

	for (int i = 0 ; i < k ; ++i)
	{
		while (!q.empty() && sir[i] < q.front())
		{
			q.pop_front();
		}
		q.push_front(sir[i]);
	}

	int sum = q.back();

	for (int i = k ; i < n ; ++i)
	{
		while (!q.empty() && sir[i] < q.front())
		{
			q.pop_front();
		}
		q.push_front(sir[i]);
		if (q.back() == sir[i - k])
		{
			q.pop_back();
		}
		sum += q.back();
	}

	printf("%d\n",sum);

	return 0;
}