Cod sursa(job #311854)

Utilizator andreea_alexAndreea Alexandru andreea_alex Data 4 mai 2009 15:17:37
Problema Deque Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include<stdio.h>

int A[10000000],d[100],v[100];
int N,K,p,u;

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()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	
	int i,s=0;
	scanf("%d%d",&N,&K);
	for(i=0;i<K;++i)
	{
		scanf("%d", &v[i]);
		dreapta(i);
	}
	s=v[d[p]];
	for(i=K;i<N;++i)
	{
			scanf("%d", &v[i]);
		stanga(i);
		dreapta(i);
		s+=v[d[p]];
	}
	printf("%d", s);
return 0;
}