Cod sursa(job #645399)

Utilizator theocmtAxenie Theodor theocmt Data 9 decembrie 2011 15:43:17
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n,l,x,h[100001],nr;
long long s;

struct pct
{
    int dist,puf;
};

pct v[100001];

bool cmp(pct x,pct y)
{
    if (x.dist <= y.dist)
        return false;
    return true;
}

void urca(int p)
{
    int aux;
    if (p>=2 && h[p] <= h[p/2])
    {
        aux=h[p/2];
        h[p/2]=h[p];
        h[p]=aux;
        urca(p/2);
    }
}

void coboara(int p)
{
    int pmax=p,aux;
    if (2*p<= nr && h[2*p] < h[pmax])
        pmax=2*p;
    if (2*p+1<= nr && h[2*p+1] < h[pmax])
        pmax=2*p+1;
    if (pmax != p)
    {
        aux=h[pmax];
        h[pmax]=h[p];
        h[p]=aux;
        coboara(pmax);
    }
}

int main()
{
    int i;
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d%d%d",&n,&x,&l);
    for (i=1; i<=n; ++i)
        scanf("%d%d",&v[i].dist,&v[i].puf);
    sort(&v[1],&v[n+1],cmp);
    for (i=1; i<=n; ++i)
    {
        if (v[i].dist <= x)
        {
            h[++nr]=v[i].puf;
            urca(nr);
            x -= l;
        }
        else
            if (nr>=1 && v[i].puf > h[1])
            {
                h[1]=v[i].puf;
                coboara(1);
            }
    }
    for (i=1; i<=nr; ++i)
        s+=h[i];
    printf("%lld\n",s);
    return 0;
}