Cod sursa(job #311850)

Utilizator dorelStoica Razvan-Andrei dorel Data 4 mai 2009 15:07:25
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<stdio.h>
#define N 5000001
int d[N],v[N],p,n,u,k;
void stanga (int i)
{
	if (i-d[p]==k)
		++p;
}
void dreapta (int i)
{
	while (p<=u && v[i]<=v[d[u]])
		--u;
	d[++u]=i;
}
int main ()
{
	int s,i;
	freopen ("deque.in","r",stdin);
	freopen ("deque.out","w",stdout);
	p=1;
	u=0;
	scanf ("%d%d",&n,&k);
	for (i=1 ; i<=n ; ++i)
	{
		scanf ("%d",&v[i]);
	}
	u=0;
	p=1;
	s=v[d[p]];
	for (i=1 ; i<=n ; ++i)
	{
		dreapta(i);
		stanga(i);
		if (i>=k)
			s+=v[d[p]];
	}
	printf ("%d",s);
	return 0;
}