Cod sursa(job #3301501)

Utilizator ibanuIoana Banu ibanu Data 27 iunie 2025 02:07:10
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
// https://infoarena.ro/problema/deque
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <deque>

using namespace std;

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

struct cmp {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.first > b.first;
    }
};

int main() {
    int n, k;
    
    f >> n >> k;
    vector<int> a(n);
    
    for (int i = 0; i < n; i++) {
        f >> a[i];
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> mind;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        mind.push({a[i], i});

        while (mind.top().second < i - k + 1) {
            mind.pop();
        }
        if (!mind.empty() && i >= k - 1) {ans += (int)mind.top().first;}
    }

    cout << ans;

    return 0;
}