Pagini recente » Cod sursa (job #2722399) | Cod sursa (job #1059316) | Cod sursa (job #1227290) | Cod sursa (job #1555803) | Cod sursa (job #2612477)
#include <iostream>
#include <fstream>
int deq[5000005];
int st = 0;
int dr = -1;
///deq [st] = deque.front()
///deq [dr] = deque.back();
void push_back(int x) {
dr++;
deq[dr] = x;
}
void pop_front() {
// se elimina primul element
st++;
}
void pop_back() {
// se elimina ultimul element
dr--;
};
int main() {
std :: ifstream fin ("deque.in");
std :: ofstream fout ("deque.out");
int n, k, v[5000005];
int suma = 0;
fin >> n >> k;
for (int i = 0; i < n; ++i) {
fin >> v[i];
}
for (int i = 0; i < n; ++i) {
// while (deque not empty and deque.back >= v[i])
while(st <= dr and v[deq[dr]] > v[i]) {
pop_back();
}
push_back(i);
// if (deque.front == i-k)
if (deq[st] == i-k) {
pop_front();
///cand s-a atins limita de k elemnete
}
if (i >= k-1) {
// std :: cout << v[deq[st]] << " " ;
suma += v[deq[st]];
}
}
fout << suma;
return 0;
}