Cod sursa(job #1027963)

Utilizator heracleRadu Muntean heracle Data 13 noiembrie 2013 12:23:47
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 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, v+n+1,cmp);

    bool b=1;
    long long sum=0;
    for(int i=0; b==1 ; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(v[j].dist+l*i <=x)
                adauga(v[j].lan);
            else
                while(v[j].lan>heap[1] && heap[1]!=0)
                    sterge(1);
        }
        if(heap[0]==0)
            break;

        while(heap[0]!=1)
        {
            sterge(1);
        }
        sum+=heap[1];
        heap[0]=0;
    }
    printf("%lld",sum);


    return 0;
}