Cod sursa(job #2183317)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 23 martie 2018 00:23:36
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.48 kb
#include <iostream>
#include <fstream>
using namespace std;

template <class T>
class Deque
{
private:
    struct nod
    {
        T info;
        nod *Next, *Back;
    }*front_point,*back_point;
public:
    Deque()
    {
        front_point = NULL;
        back_point  = NULL;
    }
    void Push_front(T x)
    {
        nod* cap = new nod;
        cap->info = x;
        cap->Next = front_point;
        cap->Back = NULL;

        if( front_point == NULL )
            front_point = back_point =  cap;
        else
        {
            front_point->Back = cap;
            front_point = cap;
        }
    }
    void Push_back(T x)
    {
        nod* cap = new nod;
        cap->info = x;
        cap->Next = NULL;
        cap->Back = back_point;

        if( back_point == NULL )
            front_point = back_point =  cap;
        else
        {
            back_point->Next = cap;
            back_point = cap;
        }
    }
    void Pop_front()
    {
        nod* cap = front_point->Next;
        delete front_point;

        if( cap == NULL )
            front_point = back_point = NULL;
        else
        {
            cap->Back = NULL;
            front_point = cap;
        }
    }
    void Pop_back()
    {
        nod* cap = back_point->Back;
        delete back_point;

        if( cap == NULL )
            front_point = back_point = NULL;
        else
        {
            cap->Next = NULL;
            back_point = cap;
        }
    }
    T Front()
    {
        if( front_point != NULL )
            return front_point->info;
    }
    T Back()
    {
        if( back_point != NULL )
            return back_point->info;
    }
    bool Empty()
    {
        if( front_point == NULL && back_point == NULL )
            return true;
        return false;
    }
};

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

#define f first
#define s second
#define mp  make_pair

long long N, K, S;
Deque< pair<int,int> > DQ; /// first-val second-index

int main()
{
    int val;
    fin >> N >> K;
    for(int i = 1 ; i <= N ; i++)
    {
        fin >> val;

        while( !DQ.Empty() && DQ.Back().f >= val )
                DQ.Pop_back();

        DQ.Push_back( mp(val, i) );

        while( !DQ.Empty() && i - DQ.Front().s >= K )
                DQ.Pop_front();

        if( i >= K )
            S += DQ.Front().f ;//, cout << DQ.Front().f << ' ';
    }

    fout << S;
    return 0;
}