Cod sursa(job #2555977)

Utilizator KPP17Popescu Paul KPP17 Data 24 februarie 2020 16:39:44
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 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];



//void print_deq() {for (int i = p; i <= u; i++) out << deq[i].val << ' '; out << "(" << p << ", " << u << ")\n";}


int main() {

    int n, k, suma = 0;

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


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

        //print_deq();

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

            suma += deq[p].val;

        }



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

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

            u--;

        }

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

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

            p++;

        }

    }

    //print_deq();



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

        suma += deq[p].val;

    }



    out << suma;

}





















//