Pagini recente » Clasament grigore-moisil-2017-clasa-10 | Cod sursa (job #694615) | Cod sursa (job #1375193) | Cod sursa (job #2921078) | Cod sursa (job #2177371)
#include <fstream>
#include <deque>
using namespace std;
ifstream fin ("deque.in");
ofstream fout ("deque.out");
const int inf = 0x3f3f3f3f;
deque <int> p, q;
int n, k, i, a, suma;
int main() {
fin >> n >> k;
for (i = 1; i <= k; ++i) {
fin >> a;
while (!q.empty() && q.back() >= a) {
q.pop_back();
p.pop_back();
}
q.push_back(a);
p.push_back(i);
}
suma += q.front();
for (i = k + 1; i <= n; ++i) {
fin >> a;
while (!q.empty() && q.back() >= a) {
q.pop_back();
p.pop_back();
}
q.push_back(a);
p.push_back(i);
while (p.front() <= i - k) {
p.pop_front();
q.pop_front();
}
suma += q.front();
}
fout << suma;
}