Cod sursa(job #645413)

Utilizator mattapoMatei Apolzan mattapo Data 9 decembrie 2011 16:06:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

int v[100001],nr;

struct oi
{
    int dst,pf;
};
oi a[1000001];
void chng (int &a,int &b)
{
    int aux;
    aux=a;
    a=b;
    b=aux;
}
bool cmp (oi a, oi b)
{
    if (a.dst > b.dst)
        return true;
    return false;
}
void urca (int x)
{
    if (x>=2 && v[x]<v[x/2])
    {
        chng (v[x],v[x/2]);
        urca (x/2);
    }
}
void coboara (int p)
{
    int pmin = p;
    if(2*p <= nr && v[2*p] < v[pmin]) pmin = 2*p;
    if(2*p + 1 <= nr && v[2*p + 1] < v[pmin]) pmin = 2*p + 1;
    if(pmin != p)
    {
        chng(v[p],v[pmin]);
        coboara(pmin);
    }
}
int main ()
{
    int n,d,l,i;
    long long s=0;
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d %d %d",&n,&d,&l);
    for (i=1;i<=n;i++)
    {
        scanf("%d %d",&a[i].dst,&a[i].pf);
    }
    sort (&a[1],&a[n+1],cmp);
    for (i=1;i<=n;i++)
    {
        if (a[i].dst<=d)
        {
            v[++nr]=a[i].pf;
            urca (nr);
            d -= l;
            continue;
        }
        if(nr>=1 && a[i].pf>v[1])
        {
            v[1] = a[i].pf;
            coboara(1);
        }
    }
    for (i=1;i<=nr;i++)
        s+=v[i];
    printf("%lld",s);
    return 0;
}