Pagini recente » Cod sursa (job #1687379) | Cod sursa (job #678583) | Cod sursa (job #1678638) | Cod sursa (job #3040857) | Cod sursa (job #1804049)
#include <deque>
#include <fstream>
using namespace std;
deque <int> D;
int a[5000005],n,k;
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",&a[i]);
}
for (int i=1;i<=k;i++){
while (!D.empty()&&a[D.back()]>a[i]){
D.pop_back();
}
D.push_back(i);
}
int s=0;
for (int i=k+1;i<=n;i++){
s+=a[D.front()];
if (D.front()<=i-k){
D.pop_front();
}
while (!D.empty()&&a[D.back()]>a[i]){
D.pop_back();
}
D.push_back(i);
}
s+=a[D.front()];
printf("%d",s);
}