Cod sursa(job #1037491)

Utilizator heracleRadu Muntean heracle Data 20 noiembrie 2013 12:07:39
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <cstdio>
#include <algorithm>
const int Q=100002;
struct oi{
    int dist,lan;
}   v[Q];

bool cmp(oi a, oi b)
{
    if(a.dist>b.dist)
        return 1;
    if(a.dist<b.dist)
        return 0;
    if(a.lan>b.lan)
        return 1;
    return 0;
}

int heap[Q];


void schimba(int p1, int p2)
{
    int aux;
    aux=heap[p1];
    heap[p1]=heap[p2];
    heap[p2]=aux;
}

void urca(int p)
{
    if(heap[p] < heap[p/2] && p>=2)
    {
        schimba(p,p/2);
        urca(p/2);
    }
}

void adauga(int x)
{
    heap[++heap[0]]=x;
    urca(heap[0]);
}

void coboara(int p)
{
    int p1=2*p,p2=2*p+1;
    if(p>p1 && p>p2)
    {
        schimba(p,p2);
        coboara(p2);
    }
    if(p>p1 && p<p2)
    {
        schimba(p,p1);
        coboara(p1);
    }

}


void sterge(int p)
{
    schimba(heap[0],p);
    heap[0]--;
    urca(p);
    coboara(p);

}


int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    int n,x,l;
    scanf("%d%d%d",&n,&x,&l);

    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&v[i].dist,&v[i].lan);
    }

    std:: sort(v+1, v+n+1,cmp);

    bool b=1;
    long long rez=0;
    int dmax=0;
    while(dmax<=x)
    {
        dmax+=l;
    }
    int dmax0;
    dmax-=l;
    dmax0=dmax;
    int i;
    for(i=1; i<=n; i++)
    {
        if(v[i].dist<=dmax)
        {
            adauga(v[i].lan);
            dmax-=l;
        }
        if(dmax<0)
            break;
    }

    int act;
    for(; i<=n ; i++)
    {

        if(v[i].lan>heap[1])
        {
            sterge(1);
            adauga(v[i].lan);
        }


        /*
        if(v[i].dist<=dmax && v[i].dist>dmax-l)
        {
            adauga(v[i].lan);
        }
        else
        {
            if(heap[0]>=1)
            {
                while(heap[1]<v[i].lan && heap[0]!=0)
                {
                    act=heap[1];
                    sterge(1);
                }
                rez+=act;
                dmax-=l;
            }
            adauga(v[i].lan);
        }

        if(heap[0]==0)
            adauga(v[i].lan);
        else
        {


        }
        */

    }
    rez=0;
    while(heap[0]!=0)
    {
        rez+=heap[1];
        sterge(1);
    }

    printf("%lld",rez);
    return 0;
}