Pagini recente » Cod sursa (job #2285117) | Cod sursa (job #385217) | Cod sursa (job #212534) | Cod sursa (job #2890731) | Cod sursa (job #373906)
Cod sursa(job #373906)
#include<cstdio>
int s,sum,d,n,k,dq[5000001],v[5000001];
inline void st(int i)
{
if(i-dq[s]==k)
++s;
}
void dr(int i)
{
while(s<=d && v[dq[d]]>=v[i])
--d;
dq[++d]=i;
}
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]);
dq[1]=1;
s=d=1;
for(int i=2;i<=k;i++)
{
st(i);
dr(i);
}
sum+=v[dq[s]];
for(int i=k+1;i<=n;i++)
{
st(i);
dr(i);
sum+=v[dq[s]];
}
printf("%d",sum);
return 0;
}