Cod sursa(job #3127561)

Utilizator barzoiusBarzoius barzoius Data 7 mai 2023 16:26:20
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <iostream>
#include <fstream>
#include <vector>

int main(){

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

    int N, K;
    fin>>N>>K;

    std::vector<int> DQ(N), V(N);
    int FIRST = 1;
    int LAST = 0;

    long long int MIN_SUM = 0;

    for(int i = 1; i <= N; i++){
        fin>>V[i];
    }

    for(int i = 1; i <= N; i++){
        while(V[i] <= V[DQ[LAST]] && FIRST <= LAST){
            LAST--;
        }
        LAST++;
        DQ[LAST] = i;

        if(DQ[FIRST] <= i - K)
            FIRST++;

        if(i >= K)
            MIN_SUM +=V[DQ[FIRST]];
    }

    fout<<MIN_SUM;

    return 0;
}