Cod sursa(job #3330584)

Utilizator OrhanZLTOrhan Zlatkov OrhanZLT Data 20 decembrie 2025 11:55:30
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second

using namespace std;

const ll MOD=1e9+7;
const string filename="deque";
ifstream fin(filename+".in");
ofstream fout(filename+".out");

int main()
{
    ll n,k,x,ans=0;
    fin>>n>>k;
    deque<pair<ll,ll>> dq;
    for(int i=0;i<n;i++){
        fin>>x;
        while(!dq.empty() && dq.back().F>=x)dq.pop_back();
        dq.push_back({x,i});
        while(!dq.empty() && dq.front().S<=i-k)dq.pop_front();
        if(k-1<=i)ans+=dq.front().F;
    }
    fout<<ans;
    return 0;
}