Cod sursa(job #298998)

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

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

long long min(long 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("%lli",&v[i]);
}


int main()
{
	long 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("%lli",s);
	return 0;
}