Cod sursa(job #309678)
Utilizator | Luca Bogdan luk17 | Data | 30 aprilie 2009 22:01:58 |
---|---|---|---|
Problema | Deque | Scor | 25 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.41 kb |
#include<stdio.h>
#define NMAX 5000001
int c[NMAX],pr,ul,a[NMAX],n,k;
long sum;
int main()
{
int i;
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
pr=1;
for(i=1;i<=n;i++)
{
for(;pr<=ul&&a[i]<=a[c[ul]];--ul);
c[++ul]=i;
if(c[pr]==i-k)
pr++;
if(i>=k)
sum+=a[c[pr]];
}
printf("%ld",sum);
return 0;
}