Pagini recente » Cod sursa (job #2393648) | Cod sursa (job #2237569) | Cod sursa (job #3220924) | Cod sursa (job #3039337) | Cod sursa (job #1980187)
#include <stdio.h>
#include <deque>
using namespace std;
deque <int> deck1;
deque <int> deck2;
long long ans;
int N, K;
int nr;
int main() {
FILE *fin = fopen("deque.in", "r");
FILE *fout = fopen("deque.out", "w");
int i, j;
fscanf(fin, "%d %d", &N, &K);
for (i = 1; i <= K; i++) {
fscanf(fin, "%d", &nr);
while (!deck1.empty() && deck1.back() > nr) {
deck1.pop_back();
deck2.pop_back();
}
deck1.push_back(nr);
deck2.push_back(i);
}
ans += deck1.front();
for (i = K + 1; i <= N; i++) {
fscanf(fin, "%d", &nr);
while (!deck1.empty() && deck1.back() > nr) {
deck1.pop_back();
deck2.pop_back();
}
deck1.push_back(nr);
deck2.push_back(i);
while (i - deck2.front() + 1 > K) {
deck1.pop_front();
deck2.pop_front();
}
ans += deck1.front();
}
fprintf(fout, "%lld\n", ans);
return 0;
}