Cod sursa(job #311859)

Utilizator nemultumitulMatei Ionita nemultumitul Data 4 mai 2009 15:20:49
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <stdio.h>

int d[5000000],v[5000000];
int p,u,n,K;

void stanga(int x)
{
	if (x-d[p]>=K)
		p++;
}

void dreapta(int x)
{
	while (p<=u&&v[x]<=v[d[u]])
		u--;
	d[++u]=x;
}

int main()
{
	freopen ("deque.in","r",stdin);
	freopen ("deque.out","w",stdout);
	
	int x,s=0;
	scanf("%d%d",&n,&K);
	for (x=0;x<K;++x)
	{
		scanf("%d",&v[x]);
		dreapta(x);
	}
	s=v[d[p]];
	for(x=K;x<n;++x)
	{
		scanf("%d",&v[x]);
		stanga(x);
		dreapta(x);
		s+=v[d[p]];
	}
	printf("%d",s);
	return 0;
}