Pagini recente » Cod sursa (job #1199731) | Cod sursa (job #2552959) | Cod sursa (job #304227) | Cod sursa (job #965338) | Cod sursa (job #1847482)
#include <cstdio>
#include <queue>
using namespace std;
const int MAX_N = 5000000;
typedef pair <int, int> ii;
int v[MAX_N];
deque <ii> q;
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]);
}
long long s = 0;
for (int i = 1; i <= N; ++i) {
while (!q.empty() && v[i] <= q.back().first) {
q.pop_back();
}
q.push_back (ii (v[i], i));
if (i >= k) {
while (!q.empty() && i - q.front().second + 1 > k) {
q.pop_front();
}
s += q.front().first;
}
}
printf ("%lld\n", s);
return 0;
}