Cod sursa(job #825235)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 27 noiembrie 2012 22:15:50
Problema Deque Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#define NMAX 5000004

using namespace std;

ifstream in("deque.in");
ofstream out("deque.out");

struct pct{int poz, val;}V[NMAX];

int N,T,P,K;

void Heap_Up(int p)
{
    if(p>1&&V[p/2].val>V[p].val)
    {
        pct aux = V[p/2];
        V[p/2] = V[p];
        V[p] = aux;
        Heap_Up(p/2);
    }
}

void Heap_Down(int p)
{
    int min = p;
    if(V[min].val>V[2*p].val&&2*p<=N)
        min = 2*p;
    if(V[min].val>V[2*p+1].val&&2*p+1<=N)
        min = 2*p+1;
    if(min != p)
    {
        pct aux = V[min];
        V[min] = V[p];
        V[p] = aux;
    }
}

void Push_Heap(pct x)
{
    V[++N] = x;
    Heap_Up(N);
}

void Pop_Heap()
{
    while(V[1].poz+K-1<=P)
        V[1] = V[N--],Heap_Down(1);
}

int main()
{
    int Sum = 0;
    pct t;
    in>>T>>K;
    for(P=1;P<=T;P++)
    {
        in>>t.val;
        t.poz = P;
        Push_Heap(t);
        if(P>=K)
            Sum+=V[1].val,Pop_Heap();
    }
    out<<Sum<<'\n';
    return 0;
}