Cod sursa(job #2724720)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 17 martie 2021 18:28:39
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <bits/stdc++.h>

using namespace std;

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

class deq {
    private:
        struct nod {
            int val;
            nod *lf, *rg;
        };

        nod *fr, *bk;
        int qsize;

    public:
        deq() {
            fr = bk = NULL;
            qsize = 0;
        }
        void pushfront( int x ) {
            nod *tmp = new nod;

            tmp -> val = x;
            tmp -> rg = fr;
            tmp -> lf = NULL;

            if( fr != NULL )
                fr -> lf = tmp;
            fr = tmp;

            ++qsize;
            if( bk == NULL ) bk = fr;
        }
        void pushback( int x ) {
            nod *tmp = new nod;

            tmp -> val = x;
            tmp -> lf = bk;
            tmp -> rg = NULL;

            if( bk != NULL )
                bk -> rg = tmp;
            bk = tmp;

            ++qsize;
            if( fr == NULL ) fr = bk;
        }
        void popfront() {
            if( qsize == 0 ) return;

            --qsize;
            nod *tmp = fr;

            fr = fr -> rg;
            if( fr )
                fr -> lf = NULL;
            delete tmp;

            if( qsize == 0 ) fr = bk = NULL;
        }
        void popback() {
            if( qsize == 0 ) return;

            --qsize;
            nod *tmp = bk;

            bk = bk -> lf;
            if( bk )
                bk -> rg = NULL;

            delete tmp;

            if( qsize == 0 ) fr = bk = NULL;
        }
        int qback() {
            if( qsize == 0 ) return -1;
            return bk -> val;
        }
        int qfront() {
            if( qsize == 0 ) return -1;
            return fr -> val;
        }
        int Qsize() {
            return qsize;
        }
};

deq Q;
int n, k;
long long sum;
int a[5000005];

int main()
{
    fin >> n >> k;

    int x;
    for( int i = 1; i <= n; ++i ) {
        fin >> a[i];

        if( Q.Qsize() && i - Q.qfront() == k )
            Q.popfront();

        while( Q.Qsize() && a[i] < a[Q.qback()] )
            Q.popback();

        Q.pushback( i );

        if( i >= k )
            sum += a[Q.qfront()];
    }

    fout << sum << '\n';

    fin.close();
    fout.close();

    return 0;
}