Pagini recente » Cod sursa (job #165545) | Cod sursa (job #2654927) | Cod sursa (job #2295958) | Cod sursa (job #443152) | Cod sursa (job #672544)
Cod sursa(job #672544)
#include <stdio.h>
#include <deque>
using namespace std;
long N, k, crt;
long long smin;
struct L {
long nr, d;
};
deque<L> q;
int main() {
long i, j;
L tmp;
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
scanf("%ld %ld", &N, &k);
scanf("%ld", &crt);
tmp.nr = crt;
tmp.d = 1;
q.push_back(tmp);
for(i = 2; i <= k; i++) {
scanf("%ld", &crt);
while(!q.empty() && crt <= q.back().nr) {
q.pop_back();
}
tmp.nr = crt;
tmp.d = i;
q.push_back(tmp);
}
smin += q.front().nr;
for(; i <= N; i++) {
scanf("%ld", &crt);
while(!q.empty() && crt <= q.back().nr) {
q.pop_back();
}
tmp.nr = crt;
tmp.d = i;
q.push_back(tmp);
if(q.back().d - q.front().d == k)
q.pop_front();
smin += q.front().nr;
}
printf("%ld", smin);
return 0;
}