Cod sursa(job #672561)

Utilizator lam99Tran Bach Lam lam99 Data 2 februarie 2012 16:15:07
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<stdio.h>
int n,k,i,p,u,a;
long long min;
struct tudi
{
	int i,v;
};
tudi dq[5000001];
int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	scanf("%d%d",&n,&k);
	p=1;
	u=1;
	scanf("%d",&a);
	dq[p].v=a;
	dq[p].i=1;

for(i=2;i<=n;i++)
	{
		scanf("%d",&a);
		if(a>dq[u].v)
		{dq[++u].v=a; dq[u].i=i;}
		if(a<dq[u].v)
		{	
			while(a<dq[u].v&&p<=u)
			{
				u--;
			}
			
			dq[++u].v=a;
			dq[u].i=i;
		}
		if(dq[u].i-dq[p].i+1>k)
			p++;
		if(i>=k)
			min=min+dq[p].v;
	}
	printf("%lld",min);
	return 0;
}