Pagini recente » Cod sursa (job #2047605) | Cod sursa (job #2777526) | Cod sursa (job #3228990) | Cod sursa (job #1456165) | Cod sursa (job #2555977)
#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];
//void print_deq() {for (int i = p; i <= u; i++) out << deq[i].val << ' '; out << "(" << p << ", " << u << ")\n";}
int main() {
int n, k, suma = 0;
in >> n >> k >> deq->val;
for (int i = 1; i < n; i++) {
//print_deq();
if (deq[u].idx >= k - 1) {
suma += deq[p].val;
}
in >> deq[i].val;
deq[i].idx = i;
while (u >= p && deq[u].val >= deq[i].val) {
u--;
}
deq[++u] = deq[i];
if (deq[u].idx - deq[p].idx == k) {
p++;
}
}
//print_deq();
if (deq[u].idx >= k - 1) {
suma += deq[p].val;
}
out << suma;
}
//