Pagini recente » Cod sursa (job #1424154) | Cod sursa (job #1956940) | Cod sursa (job #533974) | Cod sursa (job #1837290) | Cod sursa (job #2981356)
#include <cstdio>
#include <memory>
#include <queue>
#include <vector>
using namespace std;
class Solver{
private:
public:
Solver() {
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
}
~Solver() {
fclose(stdin);
fclose(stdout);
}
void execute() {
deque<int> dq;
// dq.back() - the index of the smallest value in the last K values
// dq[i] contains the indices in values in decreasing order
// values[dq[i]] contains the smallest K values in decreasing order
int N, K;
scanf("%d%d", &N, &K);
vector<int> values(N);
int total = 0;
for (int i = 0; i < N; ++i) {
scanf("%d", &values[i]);
while (!dq.empty() && values[dq.front()] >= values[i])
dq.pop_front();
dq.push_front(i);
if (!dq.empty() && i - dq.back() == K)
dq.pop_back();
if (i >= K - 1)
total += values[dq.back()];
}
printf("%d\n", total);
}
};
int main() {
unique_ptr<Solver> s = make_unique<Solver>();
s->execute();
return 0;
}