Pagini recente » Cod sursa (job #879703) | Cod sursa (job #1122578) | Cod sursa (job #2221660) | Cod sursa (job #89960) | Cod sursa (job #3126684)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int main()
{
deque <pair<int, int>> deq;
int n, k, el, sum = 0;
f >> n >> k;
for(int i = 1; i <= n; i++)
{
f >> el;
//vrem sa elimine din finalul deque-ului elementele mai mari ca el curent
while(!deq.empty() && deq.back().first > el)
deq.pop_back();
deq.push_back(make_pair(el,i)); //punem elementul si pozitia lui in deque
//pt fiecare segment care incepe de la k pana la final trebuie sa gasim un minim si sa-l adunam la secventa
if(i >= k)
{
//dam pop la minim daca nu mai e in secventa
if(deq.front().second == i - k)
deq.pop_front();
//il luam pe cel care ramane primul in deq
sum += deq.front().first;
}
}
g << sum;
return 0;
}