Cod sursa(job #374537)

Utilizator pirvupirvu tudor pirvu Data 17 decembrie 2009 13:21:08
Problema Deque Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<cstdio>

int n,k,st,dr,j,sum,min;

int dq[5000001];
int v[5000001];

inline void stanga(int i)
{
	if (dq[st]==i-k) 
		++st;
}

void dreapta (int i)
{
	while(st<=dr && v[i]<=v[dq[dr]] ) 
		--dr;
	
	dq[++dr]=i;
	
}


int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	
	scanf("%d%d", &n, &k);
	
	for (j=1;j<=n;j++)
		scanf("%d\n", &v[j]);
	
	
	
	st=1;
	dr=k;
	

	
	for (j=1;j<k;j++)
	{
		stanga(j);
		dreapta(j);
	}
	
	
	for (j=k;j<=n;j++)
	{
		stanga(j);
		dreapta(j);
		sum+=v[dq[st]];
		
	}
	
	printf("%d", sum);
	
	
	return 0;
}