Cod sursa(job #2204041)

Utilizator andrei32576Andrei Florea andrei32576 Data 14 mai 2018 10:55:27
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
#include <deque>

using namespace std;

int n,k,i,s,x;
deque< pair<int,int> > d;

ifstream f("deque.in");
ofstream g("deque.out");

void elimin(int x,int p)
{
    while(!d.size()==0 && x<d.back().first)
        d.pop_back();
    d.push_back(make_pair(x,p));
}

int main()
{
    f>>n>>k;
    s=0;

    for(i=1;i<=n;i++)
    {
        f>>x;
        elimin(x,i);
        while(!d.size()==0 && d.front().second<i-k+1)
            d.pop_front();
        if(i>=k)
            s+=d.front().first;
    }

    g<<s;

    f.close();
    g.close();
    return 0;
}