Pagini recente » Cod sursa (job #901853) | Cod sursa (job #2307849) | Cod sursa (job #2335939) | Cod sursa (job #1489677) | Cod sursa (job #2522076)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
struct entr
{
int val;
int sav;
} nrf;
deque <entr> deq;
long long int nrnr, nrk, poz = 0, sum = 0, nri;
void push(int val, int sav)
{
if (!deq.empty()) {
while (deq.front().val > val)
{
deq.pop_front();
if (deq.empty()) {
break;
}
}
}
nrf.val = val;
nrf.sav = sav;
deq.push_front(nrf);
}
int main()
{
fin >> nrnr >> nrk;
for (long long int index = 0; index < nrk; index++)
{
fin >> nri;
push(nri, index);
}
sum = deq.back().val;
for (long long int index = nrk; index < nrnr; index++)
{
fin >> nri;
push(nri, index);
if (!deq.empty()) {
while (index - deq.back().sav >= nrk)
{
deq.pop_back();
if (deq.empty()) {
break;
}
}
}
sum += deq.back().val;
}
fout << sum;
}