Cod sursa(job #3126755)

Utilizator AlezuuZugravu Alexandra-Daniela Alezuu Data 6 mai 2023 22:33:47
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

    int n, k;
    f >> n >> k;

    deque<int> dq;
    deque<int> min_dq;
    int sum = 0;

    for (int i = 0; i < n; ++i) {
        int u;
        f >> u;  /// citim numarul si il adaugam in deque-ul principal
        dq.push_back(u);

        /// stergem elementele din deque-ul minim care sunt >= u
        while (!min_dq.empty() && min_dq.back() > u) {
            min_dq.pop_back();
        }

        min_dq.push_back(u);  /// adauga u in deque-ul minim

        if (i >= k-1) {  /// daca am ajuns la k el. adaugam min la suma
            sum += min_dq.front();

            if (dq.front() == min_dq.front()) {
                min_dq.pop_front();
            }

            dq.pop_front();  /// stergem primul element din dq
        }
    }

    g<< sum << endl;

    return 0;
}