Cod sursa(job #672543)

Utilizator dariusdariusMarian Darius dariusdarius Data 2 februarie 2012 16:01:04
Problema Deque Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.48 kb
#include<stdio.h>
struct DEQUE {int a,i;};
DEQUE q[5000005];
int p,u,i;
void adaugare(int x)
{
	while(u)
	{
		if(q[u].a<x)
			break;
		u--;
	}
	q[++u].a=x;
	q[u].i=i;
}
int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	int n,k,x;p=1;u=0;
	long long s=0;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		adaugare(x);
		if(q[u].i-q[p].i==k)
			p++;
		if(i>=k)
			s=s+q[p].a;
	}
	printf("%lld\n",s);
	return 0;
}