Cod sursa(job #246765)

Utilizator SheepBOYFelix Liviu SheepBOY Data 21 ianuarie 2009 12:06:49
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<stdio.h>
#pragma pack(push,1)
int n,k,lim,dq[5000000];
long long sum;
void pop_first()
{
	for(int i=1;i<=lim;++i)
		dq[i]=dq[i+1];
	--lim;
}
void add_to_dq(int aux)
{
	int i=1;
	if(lim)
	while(aux>dq[i])
	{
		++i;
		if(i==lim+1)
			break;
	}
	lim=i;
	dq[i]=aux;
}
int main()
{
	int aux,nr=0;
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	scanf("%d%d",&n,&k);
	int anr=0;
	for(int i=1;i<=n;++i)
	{
		if(anr==k+1)
		{
			pop_first();
			anr=0;
		}
		if(nr==k)
		{
			sum+=dq[1];
			nr--;
		}
		scanf("%d",&aux);
		add_to_dq(aux);
		++anr;
		++nr;
	}
	sum+=dq[1];
	printf("%lld",sum);
	return 0;
}