Cod sursa(job #1981877)

Utilizator Andrei501Clicinschi Andrei Andrei501 Data 17 mai 2017 08:08:15
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <deque>

using namespace std;

struct salam
{
    int val,pos;
};

deque <salam> D;

int main()
{
    freopen ("deque.in","r",stdin);
    freopen ("deque.out","w",stdout);

    int n,k,i,x;
    long long S=0;
    salam a;
    scanf ("%d %d",&n,&k);

    for (i=1; i<k; i++)
    {
        scanf ("%d",&x);

        while (!D.empty()&&x<=D.front().val)
        {
            D.pop_front();
        }

        a.val=x;
        a.pos=i;
        D.push_front(a);
    }

    for (i=k; i<=n; i++)
    {
        scanf ("%d",&x);

        while (!D.empty()&&x<=D.front().val)
        {
            D.pop_front();
        }

        if (D.size()<=k)
        {
            a.val=x;
            a.pos=i;
            D.push_front(a);
        }

        if (i-D.back().pos>=k)
        {
            D.pop_back();
        }

        S+=D.back().val;
    }

    printf ("%lld\n",S);

    return 0;
}