Cod sursa(job #256911)

Utilizator MirageRobert Sandu Mirage Data 12 februarie 2009 14:32:21
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>
struct bla{
	long long inf, poz;
};
bla deque[5000];
long long start, end, act, suma;
int main () {
	FILE *in=fopen("deque.in","r");
	FILE *out=fopen("deque.out","w");
	int n,k,x;
	fscanf(in,"%d%d",&n,&k);
	fscanf(in,"%d",&x);
	start=end=1;
	deque[1].inf=x;
	deque[1].poz=1;
	act=1;
	for(int i=2;i<=n;++i){
		fscanf(in,"%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;
	}
	fprintf(out,"%lld\n",suma+deque[start].inf);
	return 0;
}