Cod sursa(job #3038548)

Utilizator Cosmin.BoeriuCosmin Boeriu George Cosmin.Boeriu Data 27 martie 2023 15:22:08
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include<fstream>
#include<deque>
using namespace std;

typedef pair<long long, long long>p;
deque<p>q;

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

int main(){
    long long n, k, i, x, suma = 0;
    fin>>n>>k;
    for( i = 1; i <= n; i++ ){
        fin>>x;
        while( !q.empty() && x < q.front().first ){
            q.pop_front();
        }
        q.push_front(make_pair(x, i));
        if(q.back().second <= i - k ){
            q.pop_back();
        }
        if( i >= k ){
            suma += q.back().first;
        }
    }
    fout<<suma;
}