Pagini recente » Cod sursa (job #2412399) | Cod sursa (job #2520776) | Cod sursa (job #480474) | Cod sursa (job #959422) | Cod sursa (job #1052863)
#include <iostream>
#include <deque>
using namespace std;
struct elmt
{
int d_time, value;
};
void fillDeque(deque<elmt> &d, int k);
void push_val(deque<elmt> &d, int k, int i);
int makeStep(deque<elmt> &d, int k, int offset);
int main()
{
freopen("deque.in", "r", stdin);
freopen("deque.out", "w", stdout);
int n, k, offset, sum = 0;
deque<elmt> deq;
cin >> n >> k;
fillDeque(deq, k);
offset = k-1;
while (offset < n)
{
sum += makeStep(deq, k, offset);
offset++;
}
cout << sum;
}
void fillDeque(deque<elmt> &d, int k)
{
for (int i = 0; i < k-1; i++)
{
push_val(d, k, i);
}
}
void push_val(deque<elmt> &d, int k, int i)
{
int val;
elmt e;
cin >> val;
if (d.empty())
{
e.value = val;
e.d_time = i + k;
d.push_back(e);
}
else
{
while (!d.empty() && d.back().value > val)
{
d.pop_back();
}
e.value = val;
e.d_time = i + k;
d.push_back(e);
}
}
int makeStep(deque<elmt> &d, int k, int offset)
{
push_val(d, k, offset);
while (!d.empty() && d.front().d_time <= offset)
{
d.pop_front();
}
return d.front().value;
}