Pagini recente » Cod sursa (job #254992) | Cod sursa (job #1928733) | Cod sursa (job #1818587) | Cod sursa (job #1045558) | Cod sursa (job #3000950)
#include <iostream>
#include <fstream>
#include <deque>
#define ll long long
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int main()
{
ll n, k;
fin >> n >> k;
deque<pair<ll, ll>> lista; // nr, pozitie
ll suma = 0;
for (ll i = 0; i < n; i++)
{
ll x;
fin >> x;
while (!lista.empty() && x <= lista.back().first)
{
lista.pop_back();
}
lista.push_back(make_pair(x, i));
// elimina nr care nu fac parte din secventa
while (!lista.empty() && lista.front().second <= i - k)
{
lista.pop_front();
}
if (i >= 2)
{
suma += lista.front().first;
}
}
fout << suma;
}
/*
9 3
-7
9
2
4
-1
5
6
7
1
0 1 2 3 4 5 6 7 8
-7 9 2 4 -1 5 6 7 1
* -7 9 2 -> -7
* 9 2 4 -> 2
* 2 4 -1 -> -1
* 4 -1 5 -> -1
* -1 5 6 -> -1
* 5 6 7 -> 5
* 6 7 1 -> 1
*/