Cod sursa(job #3210658)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 6 martie 2024 22:54:52
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

//#define fin cin
//#define fout cout

using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");

using ll = long long;

struct cv {
    int index;
    int value;
};

namespace ano {
    template<typename T>
    class deque {
    private:
        // Variables:
        list<T> l;
    public:
        // Deconstructor
        ~deque() {
            this->l.clear();
        }

        // Basic functions
        bool empty() {
            return this->l.empty();
        }

        size_t size() {
            return this->l.size();
        }

        void clear() {
            this->l.clear();
        }

        T& back() {
            return this->l.back();
        }

        T& front() {
            return this->l.front();
        }

        bool activateSum(const bool val) {
            this->doSum = val;
            this->sum = 0;
        }

        // Basic control operations

        /// Basic input operations
        void push_back(const T input) {
            this->l.push_back(input);
        }

        void push_front(const T input) {
            this->l.push_front(input);
        }

        /// Basic output operations
        void pop_back() {
            this->l.pop_back();
        }

        void pop_front() {
            this->l.pop_front();
        }
    };
}
deque<cv> dq;
ll n,k;
ll ans;
int main() {
    fin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int rd;
        fin >> rd;
        while (!dq.empty() && dq.back().value > rd) {
            dq.pop_back();
        }
        dq.push_back({i,rd});
        while (!dq.empty() && dq.front().index + k == i) {
            dq.pop_front();
        }
        if (i >= k && n >= i) {
            ans += dq.front().value;
        }
    }
    fout << ans;
    return 0;
}