Cod sursa(job #1116508)

Utilizator PlatonPlaton Vlad Platon Data 22 februarie 2014 17:08:08
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>
#include <deque>

#define maxn 5000005

using namespace std;

int n, k, a[maxn];
long long s;
deque<int> q;

void citire()
{
	freopen("deque.in", "r", stdin);

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

	for(long i=1;i<=n;i++)
	{
		scanf("%d", &a[i]);
	}
}

int main()
{
	citire();

	for(long i=1;i<=n;i++)
	{
		while(!q.empty() && a[q.back()] >= a[i])
		{
			q.pop_back();
		}
		q.push_back(i);
		if(q.front() == i-k)
		{
			q.pop_front();
		}
		if(i>=k)
		{
			s+=a[q.front()];
		}
	}

	freopen("deque.out", "w", stdout);

	printf("%lld", s);

	return 0;
}