Cod sursa(job #3126684)

Utilizator Maria_VerdesVerdes Maria-Ioana Maria_Verdes Data 6 mai 2023 20:52:34
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#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;
}