Pagini recente » Cod sursa (job #647626) | Cod sursa (job #2161431) | Cod sursa (job #1215889) | Cod sursa (job #2511412) | Cod sursa (job #821289)
Cod sursa(job #821289)
#include <cstdio>
#include <deque>
using namespace std;
int f[5000005];
deque<int> deq;
int main ( ) {
freopen("deque.in","r",stdin);
freopen("deque.out","w",stdout);
int n,k,i;
long long s=0;
scanf("%d %d",&n,&k);
for(i=1;i<=n;++i){
scanf("%d",&f[i]);
}
deq.push_front(1);
for(i=2;i<=n;++i){
for(;f[deq.back()]>f[i];){
deq.pop_back();
}
deq.push_back(i);
if(deq.front()<=i-k){
deq.pop_front();
}
if(i>=k){
s+=f[deq.front()];
}
}
printf("%lld",s);
}