Cod sursa(job #2245532)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 25 septembrie 2018 13:38:58
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.92 kb
#include <cstdio>
#include <cstdlib>

using namespace std;
/*
struct deq_el
{
    int poz, val;
    deq_el *next, *prev;
};

struct deq
{
    deq_el *cap, *coada;
};

bool isempty(deq d)
{
    return d.cap == 0;
}

void insert_front(deq &d, int val, int poz)
{
    if (!d.cap)
    {
        d.cap = (deq_el*) malloc(sizeof(deq_el));
        d.cap->next = d.cap->prev = 0;
        d.cap->val = val;
        d.cap->poz = poz;
        return;
    }
    deq_el * cr = d.cap;
    d.cap = (deq_el*) malloc(sizeof(deq_el));

    d.cap->prev = 0;
    d.cap->next = cr;
    cr->prev = d.cap;

    d.cap->poz = poz;
    d.cap->val = val;

    if (!d.coada)
        d.coada = cr;
}

void insert_back(deq &d, int val, int poz)
{
    if (!d.cap)
    {
        insert_front(d, val, poz);
        return;
    }

    deq_el *cr = d.coada;
    d.coada = (deq_el*) malloc(sizeof(deq_el));
    d.coada->next = 0;
    d.coada->prev = cr;

    d.coada->val = val;
    d.coada->poz = poz;

    if (!cr)
    {
        d.cap->next = d.coada;
        d.coada->prev = d.cap;
    }
    else
    {
        cr->next = d.coada;
    }
}

void delete_front(deq &d)
{
    if (!d.cap)
        return;

    if (!d.coada)
    {
        free(d.cap);
        d.cap = 0;
        return;
    }

    deq_el * cr = d.cap;
    d.cap = d.cap->next;
    d.cap->prev = 0;
    free(cr);

    if (d.cap == d.coada)
        d.coada = 0;
}

void delete_back(deq &d)
{
    if (!d.coada)
    {
        delete_front(d);
        return;
    }

    deq_el * cr = d.coada;
    d.coada = d.coada->prev;
    d.coada->next = 0;
    free(cr);

    if (d.cap == d.coada)
        d.coada = 0;
}

void clean_deq(deq &d, int min_poz)
{
    deq_el * cr = d.cap;
    while(cr && cr->poz < min_poz)
    {
        cr = cr->next;
        delete_front(d);
    }
}

void insert_deq(deq &d, int val, int poz)
{
    deq_el * cr = d.coada;
    if (!cr)
        cr = d.cap;

    while(cr && cr->val >= val)
    {
        cr = cr->prev;
        delete_back(d);
    }

    insert_back(d, val, poz);
}
*/
int main()
{
    freopen("deque.in", "r", stdin);
    freopen("deque.out", "w", stdout);

    int n, m, i, b = 0, f = 1;
    long long s = 0;
    scanf("%d%d", &n, &m);
    int deq[n+1], x[n+1];
    for(i=2; i<=n; ++i)
    {
        scanf("%d", &x[i]);
        while(b>=f && x[deq[b]]>=x[i])
            --b;
        deq[++b] = i;
        if(deq[f] < i-m+1)
            ++f;
        if (i>=m)
            s += x[deq[f]];
    }

   /* deq d;
    d.cap = d.coada = 0;

    for(i=1; i<m; ++i)
    {
        scanf("%d", &x);
        insert_deq(d, x, i);
    }
    for(i=m; i<=n; ++i)
    {
        scanf("%d", &x);
        clean_deq(d, i-m+1);
        insert_deq(d, x, i);

        s += d.cap->val;
    }
*/
    printf("%lld\n", s);

    fclose(stdin);
    fclose(stdout);
    return 0;
}