Cod sursa(job #1037510)

Utilizator heracleRadu Muntean heracle Data 20 noiembrie 2013 12:22:08
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 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=1;
    int act;
    while(v[i].dist>dmax)
        i--;

    int cont=0;

    for(i=1; i<=n ; i++)
    {
        if(x - v[i].dist - l*cont >= 0)
        {
            adauga(v[i].lan);
            cont++;
        }
        else
            if(v[i].lan>heap[1])
            {
                adauga(v[i].lan);
                sterge(1);
            }
    }
    rez=0;
    while(heap[0]!=0)
    {
        rez+=heap[1];
        sterge(1);
    }

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