Cod sursa(job #1116481)

Utilizator PlatonPlaton Vlad Platon Data 22 februarie 2014 16:45:22
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <stdio.h>
#include <deque>

#define maxn 5000002

using namespace std;

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

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

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

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

int main()
{
	citire();

	for(int 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("%d", s);

	return 0;
}