Cod sursa(job #2204038)

Utilizator andrei32576Andrei Florea andrei32576 Data 14 mai 2018 10:52:10
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 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;
    f>>x;
    d.push_back(make_pair(x,1));
    f>>x;
    elimin(x,2);

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

    g<<s;

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