Cod sursa(job #1037665)

Utilizator heracleRadu Muntean heracle Data 20 noiembrie 2013 16:52:53
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 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 urca(int poz){
    int aux;
    while(poz > 1 && heap[poz] < heap[poz/2]){
        aux = heap[poz];
        heap[poz] = heap[poz/2];
        heap[poz/2] = aux;
        poz /= 2;
    }
}
/*
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 poz){
    int aux, bun;
    while(2*poz <= heap[0]){
        bun = poz;
        if(2*poz <= heap[0] && heap[bun] > heap[poz*2]){
            bun = 2*poz;
        }
        if(2*poz+1 <= heap[0] && heap[bun] > heap[poz*2+1]){
            bun = 2*poz + 1;
        }
        if(bun == poz) return;
        aux = heap[poz];
        heap[poz] = heap[bun];
        heap[bun] = aux;
        poz = bun;
    }
}

/*
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);
    }
}
*/

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 cont=0;
    int i=1;
    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])
        {
            heap[1] = v[i].lan;
            coboara(1);
        }
    }
    rez=0;
    for(int i=1; i<=heap[0]; i++)
        rez+=heap[i];

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