Cod sursa(job #3330583)

Utilizator OrhanZLTOrhan Zlatkov OrhanZLT Data 20 decembrie 2025 11:52:44
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 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,ans=0;
    fin>>n>>k;
    vector<ll> v(n,0);
    deque<ll> dq;
    for(int i=0;i<n;i++){
        fin>>v[i];
    }
    for(int i=0;i<n;i++){
        while(!dq.empty() && v[dq.back()]>=v[i])dq.pop_back();
        dq.push_back(i);
        while(!dq.empty() && dq.front()<=i-k)dq.pop_front();
        if(k-1<=i)ans+=v[dq.front()];
    }
    fout<<ans;
    return 0;
}