Cod sursa(job #2378328)

Utilizator HelloWorldBogdan Rizescu HelloWorld Data 12 martie 2019 00:37:12
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream in("deque.in");
ofstream out("deque.out");
long long n,x,k,i,j,poz,ind,sum;
deque <pair<long long,int>> deq;
int main()
{
    in>>n>>k;
    for (i=1; i<=n; ++i)
    {
        in>>x;
        if (i==1)
            deq.push_back({x,i});
        else
        {
            poz=-1;
            ind=deq.size()-1;
            for (j=deq.size()-1; j>=0; --j)
            {
                if (deq[j].first>=x)
                {
                    poz=j;
                }
                else
                    break;
            }
            if (poz>=0)
            {
                while (poz<=ind)
                {
                    deq.pop_back();
                    ind--;
                }
            }
            deq.push_back({x,i});
            if (deq.front().second==i-k)
                deq.pop_front();
        }
        if (i>=k)
            sum+=deq.front().first;

    }
    out<<sum<<"\n";
}