Cod sursa(job #633266)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <deque>
using namespace std;
long n, k, i, a;
long long sum;
deque < pair < long, long > > dq;
int main() {
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
scanf("%ld %ld", &n, &k);
for (i = 1; i <= n; ++i) {
scanf("%ld", &a);
while (dq.size() > 0 && dq.back().first >= a)
dq.pop_back();
dq.push_back(make_pair(a, i));
if (dq[0].second <= i - k)
dq.pop_front();
if (i >= k)
sum += dq[0].first;
}
printf("%lld\n", sum);
return 0;
}