Cod sursa(job #754689)

Utilizator Marius96Marius Gavrilescu Marius96 Data 2 iunie 2012 21:48:54
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<cstdio>
#include<deque>
using namespace std;
deque<int> d;
long long v[5000005];

void putnr(int x)
{
	while(d.size()&&v[d.back()]>v[x])
		d.pop_back();
	d.push_back (x);
}

int main()
{
	freopen ("deque.in","r",stdin);
	freopen ("deque.out","w",stdout);
	int n,k;
	scanf ("%d%d",&n,&k);

	for(int i=0;i<n;i++)
		scanf ("%lld",v+i);
	for(int i=0;i<k;i++)
		putnr (i);

	long long s=v[d.front()];
	for(int i=k;i<n;i++){
		putnr (i);
		while(d.front()<=i-k)
			d.pop_front();
		s+=v[d.front()];
	}
	printf ("%lld",s);
	return 0;
}