Cod sursa(job #341581)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 18 august 2009 21:34:51
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>
#define N 5000005
int n,k,deq[N],x,v[N];
long long sum;
int inc,sf;
void capat(int i)
{
	if (i-deq[inc]>=k)
		inc++;
}
void actualizare(int i)
{
	while (inc!=sf && v[i]<=v[deq[sf-1]])
		--sf;
	deq[sf++]=i;
}
void solve()
{
	int i;
	for (i=1; i<=k; i++)
	{
		scanf("%d",&v[i]);
		actualizare(i);
	}
	sum=v[deq[inc]];
	for (i=k+1; i<=n; i++)
	{
		scanf("%d",&v[i]);
		actualizare(i);
		capat(i);
		sum+=v[deq[inc]];
	}
}
int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	scanf("%d%d",&n,&k);
	solve();
	printf("%lld\n",sum);
	return 0;
}