Cod sursa(job #2264835)

Utilizator HoratioHoratiu Duma Horatio Data 20 octombrie 2018 11:52:34
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <deque>

using namespace std;

struct element
{
    long long poz,val;
};

deque<element> a;

int main()
{
    //freopen("deque.in","r",stdin);
    //freopen("deque.out","w",stdout);
    int s=0,n,k;
    scanf("%d %d",&n,&k);
    long long d;
    element e,f;
    for(int i=0;i<k-1;i++)
    {
    scanf("%lld",&d);
    e.poz=i;
    e.val=d;
    a.push_back(e);
    }

    for(int i=k-1;i<n;i++)
    {
    scanf("%lld",&d);
    e=a.back();
    while(e.val>d && (!a.empty()))
    {
        a.pop_back();
        if(!a.empty())
            e=a.back();
    }
    e.val=d;
    e.poz=i;
    a.push_back(e);

    e=a.back();
    f=a.front();
    while(e.poz-f.poz>=k)
    {
        a.pop_front();
        f=a.front();
    }
    s+=f.val;
    }
    printf("%d",s);
    return 0;
}