Cod sursa(job #3225606)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 18 aprilie 2024 09:39:39
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

ifstream f ("deque.in");
ofstream g ("deque.out");

deque <pair<int, int>> D;

int main()
{
    int N, K, a;
    f >> N >> K;
    long long sMin = 0;
    for (int i=1; i<=N; i++) {
        f >> a;
        while(!D.empty() && a <= D.back().first)
            D.pop_back();
        D.push_back({a, i});
        if (i >= K) {
            if (D.front().second == i-K)
                D.pop_front();
            sMin += D.front().first;
        }
    }
    g << sMin;
    return 0;
}