Cod sursa(job #2671499)

Utilizator Alex_DiaconuDiaconu Alexandru Alex_Diaconu Data 12 noiembrie 2020 11:09:29
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <deque>
#include <utility>

using namespace std;

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

deque<pair<int,int> > D;

int main()
{
    int n, x, k;
    long long r=0;
    cin >> n >> k;
    for(int i=1; i<=n; i++)
    {
        cin >> x;
        while(!D.empty() && D.back().first>x)
        {
            D.pop_back();
        }
        D.push_back(make_pair(x,i));
        if(D.front().second<=i-k)
        {
            D.pop_front();
        }
        if(i>=k)
        {
            r+=D.front().first;
        }
    }
    cout << r;
    return 0;
}