Cod sursa(job #3174655)

Utilizator SpadoveskyTuros Robert Daniel Spadovesky Data 25 noiembrie 2023 08:22:18
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

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

int main () {
    int n, k;
    long long sum = 0;
    fin >> n >> k;
    vector <int> v(n);
    deque <int> dq;

    for (int i = 0; i < n ; i++) {
        fin >> v[i];
        //dq.front == stanga
        //dq.back == dreapta
        if(!dq.empty() && dq.front() == i - k ){
            // daca elementul din stanga iese din parametrii dati, il stergem
            dq.pop_front();   
        }
        //eliminam elemente daca oricum nu mai pot fi minime, de ex 8 1 7 => 1
        while(!dq.empty() && v[i] <= v[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
       if(i >= k - 1) {
        // daca deque-ul este destul de lung
        sum += v[dq.front()];
       }
    }
    fout << sum << endl;
}