Cod sursa(job #1981753)

Utilizator Andrei501Clicinschi Andrei Andrei501 Data 16 mai 2017 18:14:50
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <deque>

using namespace std;

deque <int> D1,D2;

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

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

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

        while (!D1.empty()&&x<=D1.front())
        {
            D1.pop_front();
            D2.pop_front();
        }

        if (D1.size()<=k)
        {
            D1.push_front(x);
            D2.push_front(i);
        }

        if (D2.front()-D2.back()>=k)
        {
            D1.pop_back();
            D2.pop_back();
        }

        if (i>=k)
        {
            S+=D1.back();
        }
    }

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

    return 0;
}