Cod sursa(job #3126697)

Utilizator stefanmo03Mocanu Stefan stefanmo03 Data 6 mai 2023 21:17:41
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.68 kb
//#include <iostream>
#include <fstream>
#include <string>

using namespace std;
std::ifstream cin("alibaba.in");
std::ofstream cout("alibaba.out");
class node{
    int val,index;
    node *next,*prev;
public:
    node(int v, int index):val(v),index(index),next(nullptr),prev(nullptr){}
    int getVal(){
        return val;
    }

    node *getNext() const {
        return next;
    }

    int getIndex() const {
        return index;
    }

    void setIndex(int index) {
        node::index = index;
    }

    void setNext(node *next) {
        node::next = next;
    }

    node *getPrev() const {
        return prev;
    }

    void setPrev(node *prev) {
        node::prev = prev;
    }
};
class deque{
    node *front,*back;
public:
    deque(){
        front = nullptr;
        back = nullptr;
    }
    void push_front(int x,int index){
        if(back == nullptr){
            back = new node( x,  index);
            front = back;
            return;
        }
        else{
            node * aux = new node(x,index);
            aux->setNext(front);
            front->setPrev(aux);
            front=aux;
        }
    }
    void push_back(int x,int index){
        if(back == nullptr){
            back = new node( x, index);
            front = back;
            return;
        }
        else{
            node * aux = new node( x, index);
            aux->setPrev(back);
            back->setNext(aux);
            back=aux;
        }
    }
    void pop_back(){
        if(back->getPrev()){
            back = back->getPrev();
            delete back->getNext();
            back->setNext(nullptr);
        }else{
            delete back;
            back = nullptr;
            front = nullptr;
        }
    }
    void pop_front(){
        if(front->getNext()){
            front = front->getNext();
            delete front->getPrev();
            front->setPrev(nullptr);
        }else{
            delete front;
            front = nullptr;
            back = nullptr;
        }
    }
    node* Front(){
        return front;
    }
    node* Back(){
        return back;
    }
    bool empty(){
        return front==nullptr;
    }
};

int main() {
    deque dq;
    int sum=0,n,k,curent;
    cin>>n>>k;
    for(int i=0;i<k-1;i++){
        cin>>curent;
        while(!dq.empty() && curent < dq.Back()->getVal())dq.pop_back();
        dq.push_back(curent,i);
    }
    for(int i=k-1;i<n;i++){
        cin>>curent;
        while(!dq.empty() && curent < dq.Back()->getVal())dq.pop_back();
        dq.push_back(curent,i);
        while(!dq.empty() && i-dq.Front()->getIndex() >= k)
            dq.pop_front();
        sum+=dq.Front()->getVal();

        //cout<<dq.Front()->getVal()<<" ";
    }
    cout<<sum;
    return 0;
}