Cod sursa(job #3128494)

Utilizator dra_soloSolomon Dragos dra_solo Data 9 mai 2023 17:34:10
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <stack>
using namespace std;

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

int main() {
    int n, k;
    fin >> n >> k;

    int a[n];
    for (int i = 0; i < n; i++) {
        fin >> a[i];
    }

    stack<int> st;
    int sum_min = 0;
    for (int i = 0; i < n; i++) {
        // eliminam elementele care nu se afla in subsecventa curenta
        while (!st.empty() && st.top() > a[i]) {
            st.pop();
        }
        // adaugam elementul curent in stack
        st.push(a[i]);
        // daca am format o subsecventa completa
        if (i >= k - 1) {
            // adaugam minimul in suma
            sum_min += st.top();
            // eliminam primul element din subsecventa
            if (st.top() == a[i - k + 1]) {
                st.pop();
            }
        }
    }

    fout << sum_min << endl;

    return 0;
}