Pagini recente » Cod sursa (job #2073425) | Cod sursa (job #3126755)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
int main() {
ifstream f("deque.in");
ofstream g("deque.out");
int n, k;
f >> n >> k;
deque<int> dq;
deque<int> min_dq;
int sum = 0;
for (int i = 0; i < n; ++i) {
int u;
f >> u; /// citim numarul si il adaugam in deque-ul principal
dq.push_back(u);
/// stergem elementele din deque-ul minim care sunt >= u
while (!min_dq.empty() && min_dq.back() > u) {
min_dq.pop_back();
}
min_dq.push_back(u); /// adauga u in deque-ul minim
if (i >= k-1) { /// daca am ajuns la k el. adaugam min la suma
sum += min_dq.front();
if (dq.front() == min_dq.front()) {
min_dq.pop_front();
}
dq.pop_front(); /// stergem primul element din dq
}
}
g<< sum << endl;
return 0;
}