Cod sursa(job #3209173)

Utilizator prares06Papacioc Rares-Ioan prares06 Data 2 martie 2024 09:50:40
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.49 kb
#include<bits/stdc++.h>

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

int n, k, x;
long long sum;
std::deque<std::pair<int, int> > DQ;

int main(){
    fin >> n >> k;
    for(int i = 1; i <= n; ++i){
        fin >> x;
        while(!DQ.empty() and x < DQ.back().first){
            DQ.pop_back();
        }
        DQ.push_back({x, i});
        if(i - DQ.front().second >= k)
            DQ.pop_front();
        if(i >= k)
            sum += DQ.front().first;
    }
    fout << sum;
}