Pagini recente » Cod sursa (job #2797467) | Cod sursa (job #2306120)
#include <bits/stdc++.h>
#define int long long
const int MV(5000005) ;
int dq[MV] ;
int v[MV], s ;
int32_t main() {
freopen("deque.in", "r", stdin) ;
freopen("deque.out", "w", stdout) ;
int n, k ;
register int i ;
int st(0), dr(-1) ;
scanf("%lld %lld", &n, &k) ;
for (i = 1 ; i <= n ; ++ i) {
scanf("%lld", v + i) ;
if (st <= dr && dq[st] == i - k) {
st ++ ;}
while (st <= dr && v[i] <= v[dq[dr]]) {
dr -- ;}
dq[++ dr] = i ;
if (i >= k) {
s += v[dq[st]] ;}}
printf("%lld", s) ;
return 0 ;}