Pagini recente » Cod sursa (job #2788803) | Cod sursa (job #1705750) | Cod sursa (job #2457890) | Cod sursa (job #210533) | Cod sursa (job #3310438)
#include <cstdio>
#include <deque>
using namespace std;
const int NMAX = 5000005;
int v[NMAX];
int main() {
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int n, k;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]);
}
deque<int> dq;
for (int i = 1; i <= k; i++) {
while (!dq.empty() && v[dq.back()] >= v[i]) {
dq.pop_back();
}
dq.push_back(i);
}
long long int sume_minime = (long long int)v[dq.front()];
for (int i = k + 1; i <= n; i++) {
while (!dq.empty() && v[dq.back()] >= v[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i - k + 1 > dq.front()) {
dq.pop_front();
}
if (!dq.empty()) {
sume_minime += (long long int) v[dq.front()];
}
}
printf("%lld ",sume_minime);
return 0;
}