Cod sursa(job #3349232)

Utilizator fanceapaMosul Tudor fanceapa Data 26 martie 2026 18:18:02
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <deque>
#include <vector>
using namespace std;

long long minSubsequences(const vector<int>& v, const int n, const int k) {
    deque <int> d;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        while (!d.empty() && v[d.back()] >= v[i]) {
            d.pop_back();
        }
        d.push_back(i);
        if (d.front() <= i - k) {
            d.pop_front();
        }
        if (i >= k - 1) {
            sum += v[d.front()];
        }
    }
    return sum;
}

int main() {
    ifstream fin("deque.in");
    ofstream fout("deque.out");
    int n, k;
    fin >> n >> k;
    vector <int> v(n);
    for (int i = 0; i < n; i++)
        fin >> v[i];
    fout << minSubsequences(v, n, k);
    return 0;
}