Cod sursa(job #305049)
Utilizator | Barcau Tomsa utcistu | Data | 16 aprilie 2009 00:49:13 |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | c | Status | done |
Runda | Arhiva educationala | Marime | 0.57 kb |
#include <stdio.h>
#include <stdlib.h>
#define NMAX 5000001
int deque[NMAX],v[NMAX];
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,k,i,x,st=1,dr=0;
long long sum=0;
scanf("%d %d",&n,&k);
for (i=1;i<=n;i++)
{
scanf("%d",&x);
while (st<=dr && i-v[st]>=k) st=st+1;
while (st<=dr && x-deque[dr]<=0) dr=dr-1;
deque[++dr]=x;
v[dr]=i;
if (i>=k) sum+=deque[st];
}
printf("%lld",sum);
fclose(stdout);
fclose(stdin);
return 0;
}