Cod sursa(job #3243826)

Utilizator EricRaiaEricRaia EricRaia Data 21 septembrie 2024 16:15:48
Problema Deque Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

ifstream cin ("deque.in");
ofstream cout ("deque.out");

deque<pair<long long, long long>> coada;
long long s,n,k,i;

int main()
{
    cin>>n>>k;
    vector<int> v(n+1);
    for(i=1;i<=n;i++)
        cin>>v[i];
    for(i=1;i<=k;i++){
        while(!coada.empty() && coada.back().first>=v[i])
            coada.pop_back();
        coada.push_back({v[i], i});
    }
    s+=coada.front().first;
    for(i=k+1;i<=n;i++){
        while(!coada.empty() && coada.back().first>=v[i])
            coada.pop_back();
        coada.push_back({v[i], i});
        while(!coada.empty() && coada.front().second<=i-k)
            coada.pop_front();
        s+=coada.front().first;
    }
    cout<<s;

    return 0;
}