Cod sursa(job #3127445)

Utilizator barzoiusBarzoius barzoius Data 7 mai 2023 15:38:16
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <vector>

struct DEQUE{

    DEQUE() {}

    void push_back(int NR){
        DQ.push_back(NR);
    }

    int back() const{
        return DQ.back();
    }

    int front() const {
        return DQ.front();
    }

    bool empty() const {
        return DQ.empty();
    }

    void pop_back(){
       DQ.pop_back();
    }

    void pop_front(){
      DQ.erase(DQ.begin());
    }

private:
    std::vector<int> DQ;

};
int main() {

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

    int n, k;
    fin >> n >> k;

    DEQUE D;
    int A[n], min_sum = 0;

    for (int i = 0; i < n; i++) {
        fin >> A[i];
    }

    for (int i = 0; i < k; i++) {
        while (!D.empty() && A[i] < A[D.back()]) {
            D.pop_back();
        }
        D.push_back(i);
    }
    min_sum += A[D.front()];

    for (int i = k; i < n; i++) {
        while (!D.empty() && D.front() <= i - k) {
            D.pop_front();
        }
        while (!D.empty() && A[i] < A[D.back()]) {
            D.pop_back();
        }
        D.push_back(i);
        min_sum += A[D.front()];
    }

    fout << min_sum << std::endl;
    fout.close();
    return 0;
}