Cod sursa(job #1040989)

Utilizator cldmeClaudiu Ion cldme Data 25 noiembrie 2013 12:22:37
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int const N=100001;
int nh,h[N];

struct elem{
    int d,ln;
};
elem v[N];

bool cmp(elem a,elem b)
{
    return a.ln>b.ln;
}

void schimba(int a,int b)
{
    int aux;
    aux=h[a];
    h[a]=h[b];
    h[b]=aux;
}

void urca(int p)
{
    while(h[p]<h[p/2] && p>1)
    {
        schimba(p,p/2);
        p/=2;
    }
}

void coboara(int p)
{
    int fs=2*p,fd=2*p+1,bun=p;
    if(fs<=nh && h[fs]<h[bun]) bun=fs;
    if(fd<=nh && h[fd]<h[bun]) bun=fd;
    if(bun!=p)
    {
        schimba(bun,p);
        coboara(bun);
    }
}

void adaug(int x)
{
    h[++nh] = x;
    urca(nh);
}

int main()
{
    int i,n,x,l,nr=0;
    long long sum=0;
    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].d,&v[i].ln);
    sort(v+1,v+n+1,cmp);

    for(i=1;i<=n;i++)
    {
        if(x-(v[i].d+l*nr)>=0)
        {
            sum+=v[i].ln;
            adaug(v[i].ln);
            nr++;
        }
        else
        {
            if(v[i].ln>h[1])
            {
                sum=sum-h[1]+v[i].ln;
                h[1]=v[i].ln;
                coboara(1);
            }
        }
    }
    printf("%d",sum);
    return 0;
}