Pagini recente » Cod sursa (job #908620) | Cod sursa (job #3141657) | Cod sursa (job #843411) | Cod sursa (job #3183174) | Cod sursa (job #3167195)
#include <iostream>
#include <deque>
using namespace std;
deque<pair<int, int> > dq;
int main()
{
FILE *fin, *fout;
fin = fopen("deque.in", "r");
fout = fopen("deque.out", "w");
int n, k, sum, i, x;
fscanf(fin, "%d %d", &n, &k);
sum = 0;
for (i = 0; i < n; i++) {
fscanf(fin, "%d", &x);
if (!dq.empty() && dq.front().second <= i - k) {
dq.pop_front();
}
while (!dq.empty() && dq.back().first > x) {
dq.pop_back();
}
dq.push_back(make_pair(x, i));
if (i >= k - 1)
sum += dq.front().first;
}
fprintf(fout, "%d\n", sum);
fclose(fin);
fclose(fout);
return 0;
}