Cod sursa(job #349986)
Utilizator | Data | 22 septembrie 2009 09:09:23 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include<stdio.h>
#define Nmax 5000010
int v[Nmax],deque[Nmax],N,K,st,dr;
long long S; ;
int main()
{
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
scanf("%d%d",&N,&K);
for(int i=1;i<=N;++i)
scanf("%d",&v[i]);
st=1;
dr=0;
for(int i=1;i<=N;++i)
{
while(st<=dr && v[i]<=v[deque[dr]])
--dr;
deque[++dr]=i;
if(deque[st]==i-K)
++st;
if(i>=K)
S=S+v[deque[st]];
}
printf("%lld",S);
return 0;
}