Cod sursa(job #1066473)

Utilizator andreeaghetuUNIBUC andreeaghetu andreeaghetu Data 24 decembrie 2013 21:32:01
Problema Deque Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("deque.in");
ofstream out ("deque.out");

struct structura
{
    int valoare;
    int pozitie;
};

void swap (structura &a, structura &b)
{
    structura t=a;
    a=b;
    b=t;
}

int minim (structura a, structura b, int i)
{
    if (a.valoare>b.valoare)
        return 2*i+1;
    else
        return 2*i;
}
void up(structura *v, int i)
{

    while (i!=1 && v[i].valoare<v[i/2].valoare)
    {
        swap (v[i], v[i/2]);
        i=i/2;
    }
}
void push (structura *v, int poz, structura val)
{
    v[poz]=val;
    up(v, poz);
}

void down(structura *v, int i, int N)
{
    if (2*i>N)
        return;
    else
    {
        if (2*i+1<=N)
        {
            int poz=minim(v[2*i], v[2*i+1], i);
            if (v[poz].valoare>=v[i].valoare)
                return;
            else
            {
                swap (v[i], v[poz]);
                down (v, poz, N);
            }

        }
        else
        {
            if (v[2*i].valoare>=v[i].valoare)
                return;
            else
            {
                swap (v[i], v[2*i]);
                return;
            }
        }
    }
}

void pop (structura *v, int N)
{
    v[1]=v[N];
    down(v, 1, N);
}

int main()
{

    int N;
    structura v[260258], aux;
    int K;
    in>>N>>K;
    long long int suma=0;
    int lungime_heap=0;
    for (int i=1;i<K;++i)
    {

        in>>aux.valoare;
        aux.pozitie=i;
        push(v, i, aux);
        ++lungime_heap;
    }
    for (int i=K;i<=N;++i)
    {
        in>>aux.valoare;
        aux.pozitie=i;
        push(v, i, aux);
        ++lungime_heap;
        while (i-v[1].pozitie>=K)
        {
            pop(v, lungime_heap);
        }
        suma+=v[1].valoare;
    }

    out<<suma;
    return 0;
}