Cod sursa(job #2562237)

Utilizator KPP17Popescu Paul KPP17 Data 29 februarie 2020 12:57:59
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#define fisier "deque"

#ifdef consola

    #include <iostream>
    #define in std::cin
    #define out std::cout

#else

    #include <fstream>

    #ifndef fisier
        #define fisier "HYPER"
    #endif

    std::ifstream in(fisier ".in");
    std::ofstream out(fisier ".out");

#endif



struct Poz {int val, idx;};

#include <deque>
std::deque<Poz> deq;



int main() {

    int n, k, val;
    long long suma = 0;

    in >> n >> k >> val;

    deq.push_back({val, 0}); // deq.push_front({val, 0});



    for (int idx = 1; idx < n; idx++) {

        if (deq.back().idx >= k - 1) {

            suma += deq.front().val;

        }



        in >> val;

        while (!deq.empty() && deq.back().val >= val) {

            deq.pop_back();

        }

        deq.push_back({val, idx});

        if (deq.back().idx - deq.front().idx == k) {

            deq.pop_front();

        }

    }



    if (deq.back().idx >= k - 1) {

        suma += deq.front().val;

    }



    out << suma;

}