Cod sursa(job #283952)
Utilizator | Data | 20 martie 2009 20:50:17 | |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include <stdio.h>
int v[5000001],deque[5000001];
int n,k,i,dr,st=1;
long long s;
int main ()
{
freopen ("deque.in","r",stdin);
freopen ("deque.out","w",stdout);
scanf ("%d %d",&n,&k);
for (i=1;i<=n;i++){
scanf ("%d",&v[i]);
while (v[i]<v[deque[dr]] && st<=dr) dr--;
deque[++dr]=i;
if (deque[st]==i-k) st++;
if (i>=k) s=1LL*(s+v[deque[st]]);
}
printf ("%I64d",s);
return 0;
}