Cod sursa(job #298971)

Utilizator alisssiaMititelu Andra alisssia Data 6 aprilie 2009 15:11:06
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
using namespace std;
#include<stdio.h>
#include<deque>
#define nmax 5000001
deque<long>Q;
long k,n,v[nmax],s=0;

void push(long p)
{
	while(!Q.empty() && v[Q.back()]>v[p]) Q.pop_back();
	Q.push_back(p);
}

long min(long i)
{
	while(i-Q.front()+1>k) Q.pop_front();
	return Q.front();
}

void read()
{
	freopen("deque.in","r",stdin);
	scanf("%li%li",&n,&k);
	for(long i=0;i<n;i++)
	scanf("%li",&v[i]);
}


int main()
{
	long i;
	read();
	for(i=0;i<n;i++)
	{
		push(i);
		if(i+1>=k) s+=v[min(i)];
	}
	freopen("deque.out","w",stdout);
	printf("%li",s);
	return 0;
}