Cod sursa(job #256909)

Utilizator MirageRobert Sandu Mirage Data 12 februarie 2009 14:28:10
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<stdio.h>
struct bla{
	long inf, poz;
};
bla deque[5000];
long start, end, act, suma;
int main () {
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	long n,k,x;
	scanf("%ld%ld",&n,&k);
	scanf("%ld",&x);
	start=end=1;
	deque[1].inf=x;
	deque[1].poz=1;
	act=1;
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		if(i-act==k){
			suma+=deque[start].inf;
			if(deque[start].poz==act)
				++start;
			
			++act;
		}
		while(start <= end && x < deque[end].inf)
			--end;
		deque[++end].inf=x;
		deque[end].poz=i;
	}
	printf("%ld\n",suma+deque[start].inf);
	return 0;
}