Cod sursa(job #2553123)

Utilizator KPP17Popescu Paul KPP17 Data 21 februarie 2020 17:25:48
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#define fisier "deque"

#ifdef fisier
    #include <fstream>
    std::ifstream in(fisier ".in");
    std::ofstream out(fisier ".out");
#else
    #include <iostream>
    #define in std::cin
    #define out std::cout
#endif



struct Elem {int idx, val;} deq[5000000];

int n, p, u, k;

int main() {

    in >> n >> k;

    long long iter, suma = 0;

    u = -1;

    for (int i = 0; i < n; i++) {

        in >> iter;

        while (p <= u && deq[u].val >= iter) {

            u--;

        }

        u++;
        deq[u].val = iter;
        deq[u].idx = i;

        if (deq[u].idx - deq[p].idx == k) {

            p++;

        }

        if (deq[u].idx >= k - 1) {

            suma += deq[p].val;

        }

    }

    out << suma;

}









//