Pagini recente » Cod sursa (job #1221942) | Cod sursa (job #1365534) | Cod sursa (job #1432847) | Cod sursa (job #481626) | Cod sursa (job #249390)
Cod sursa(job #249390)
#include <cstdio>
#define ll long long
int N, K;
int Dq[500005], V[500005];
ll ans;
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", V + i);
for (int st = 1, dr = 0, i = 1; i <= N; ++ i) {
while (st <= dr && V[Dq[dr]] >= V[i]) -- dr;
Dq[++dr] = i;
while (st <= dr && i - Dq[st] >= K) ++ st;
if (i >= K) ans += (ll)V[Dq[st]];
}
printf ("%lld\n", ans);
return 0;
}