Cod sursa(job #3216100)

Utilizator radu._.21Radu Pelea radu._.21 Data 15 martie 2024 17:22:12
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
int v[5000001];
#define int long long
deque<int>Q;
int rez = 0;
ifstream fin("deque.in");
ofstream fout("deque.out");
int n;
int32_t main(){
    /// le tin in ordine crescatoare dupa indice si descresc
    /// dupa valoare
    int k ;
    fin>>n>>k;
   // vector<int>rez;
    for(int i=1;i<=n;i++){
        int x; fin>>x;

            /// scot ce e in plus din fata
            while(!Q.empty() && Q.back()<=i-k)
                Q.pop_back();
            while(!Q.empty() && x < v[Q.front()])
                Q.pop_front();
            Q.push_front(i);
            if(i>=k)
                rez += v[Q.back()];

    }
    fout<<rez;
    return 0;
}