Cod sursa(job #2723656)

Utilizator mirceaisherebina mircea mirceaishere Data 15 martie 2021 11:32:18
Problema Deque Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;

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


struct Node{

    int value;
    Node* nextNode;

};


class Deque{

    Node* firstNode;
    Node* lastNode;

public:

    Deque(){
        firstNode = NULL;
        lastNode = NULL;
    }

    void push(int value){
        Node* newNode = new Node;
        newNode -> value = value;
        newNode -> nextNode = NULL;
        if (firstNode == NULL){
            firstNode = newNode;
            lastNode = newNode;
        }else{
            lastNode -> nextNode = newNode;
            lastNode = lastNode -> nextNode;
        }
    }

    void pop(){
        if(firstNode != NULL){
            Node* aux = firstNode -> nextNode;
            delete firstNode;
            firstNode = aux;
        }
    }


    int getMin(){
        int sol = 1000000000;
        Node* node = firstNode;
        while (node != NULL){
            sol = min(sol, node -> value);
            node = node -> nextNode;
        }
        return sol;
    }

    int getSize(){
        int sol = 0;
        Node* node = firstNode;
        while (node != NULL){
            sol++;
            node = node -> nextNode;
        }
        return sol;
    }

};



int main(){
    int n, k, x;
    int sol = 0;
    Deque d;
    fin >> n >> k;
    for (int i = 1; i <= n ; i++){
        fin >> x;
        d.push(x);
        if (d.getSize() > k){
            d.pop();
        }
        if (d.getSize() == k){
            sol += d.getMin();
        }
    }
    fout << sol;

}