Cod sursa(job #257372)

Utilizator zlatebogdanZlate Bogdan zlatebogdan Data 13 februarie 2009 09:37:59
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#define N 5000005
#define MAX 10000003
int n,k,a[N],dq[N],p,u;
void citire()
{
	int i;
	scanf("%d%d",&n,&k);
	for (i=0;i<n;++i)
		scanf("%d",&a[i]);
}
void dreapta(int x)
{
	while (u!=p&&a[dq[u-1]]>=a[x])
		--u;
	dq[u++]=x;
}
void stanga(int x)
{
	if (x-dq[p]>=k)
		++p;
}
void afisare(int x[N])
{
	int i;
	for(i=0;i<n;++i)
		printf("%d ",x[i]);
}
void solve()
{
	int min=MAX,s=0,i;
	citire();
//	afisare(a);
	dq[u++]=0;
	for (i=1;i<k;++i)
		dreapta(i);
	s=a[dq[p]];
//	printf("%d %d\n",s,a[dq[p]]);
	for (i=k;i<n;++i)
	{
		stanga(i);
		dreapta(i);
		s+=a[dq[p]];
//		printf("%d %d %d\n",s,dq[p],a[dq[p]]);
	}
	printf("%d\n",s);
		
}
int main()
{
	freopen("deque.in","r",stdin);
	freopen("deque.out","w",stdout);
	solve();
	return 0;
}