Cod sursa(job #2876675)

Utilizator AndreeaCreitaCreita Andreea AndreeaCreita Data 23 martie 2022 13:35:33
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
 #include <bits/stdc++.h>
 using namespace std;


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

int main () {

    // 1. Primul element din deque o sa fie mereu minimul
    // 2. Toate elementele din deque sunt in ordine crescatoare
    // 3. Extragem elemente din ambele capete si inseram doar in capatul dreapta
int n,k;
    deque<int> myd;
     in>>n>>k;
   int answer;
   int v[10005];
    for(int i=1; i<=n; i++)
     {
         in>>v[i];
     }

    for(int i = 1; i <= n; i++) {
        while(!myd.empty() && v[i] <= v[myd.back()]) {
            myd.pop_back();
        }

        myd.push_back(i);
        if(i >= k) {
            answer += v[myd.front()];
            if(myd.front() == i - k + 1) {
                myd.pop_front();
            }
        }
    }

    out<<answer<<" ";

    return 0;
}