Cod sursa(job #2555208)

Utilizator KPP17Popescu Paul KPP17 Data 23 februarie 2020 19:53:06
Problema Deque Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 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



const int MAX_N = 5000000;

int p, u;

struct {int val, idx;} deq[MAX_N];



int main() {

    int n, k, suma = 0;

    in >> n >> k >> deq->val;


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

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

            //out << deq[p].val << ' ';

            suma += deq[p].val;

        }



        in >> deq[i].val;
        deq[i].idx = i;

        while (u >= 0 && deq[u].val >= deq[i].val) {

            u--;

        }

        deq[++u] = deq[i];

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

            //out << "(p++) ";

            p++;

        }

    }



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

        //out << deq[p].val << ' ';

        suma += deq[p].val;

    } //out << '\n';



    out << suma;

}





















//