Pagini recente » Cod sursa (job #1224189) | Cod sursa (job #3312327) | Cod sursa (job #1416984) | Cod sursa (job #1432500) | Cod sursa (job #3310437)
#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);
}
int sume_minime = 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 += v[dq.front()];
}
}
printf("%d ",sume_minime);
return 0;
}