Pagini recente » Cod sursa (job #2773358) | Cod sursa (job #353425) | Cod sursa (job #1826507) | Cod sursa (job #1360494) | Cod sursa (job #2555208)
#define fisier "deque"
#ifdef consola
#include <iostream>
#define in std::cin
#define out std::cout
#else
#include <fstream>
#ifndef fisier
#define fisier "HYPER"
#endif
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
#endif
const int MAX_N = 5000000;
int p, u;
struct {int val, idx;} deq[MAX_N];
int main() {
int n, k, suma = 0;
in >> n >> k >> deq->val;
for (int i = 1; i < n; i++) {
if (deq[u].idx >= k - 1) {
//out << deq[p].val << ' ';
suma += deq[p].val;
}
in >> deq[i].val;
deq[i].idx = i;
while (u >= 0 && deq[u].val >= deq[i].val) {
u--;
}
deq[++u] = deq[i];
if (deq[u].idx - deq[p].idx == k) {
//out << "(p++) ";
p++;
}
}
if (deq[u].idx >= k - 1) {
//out << deq[p].val << ' ';
suma += deq[p].val;
} //out << '\n';
out << suma;
}
//