Cod sursa(job #1033862)

Utilizator george_stelianChichirim George george_stelian Data 17 noiembrie 2013 15:57:02
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct lup
{
    int a,b;
};

lup v[100010],aux;
long long int h[100010],s;
int a,b,i,nr,k,mid,d,x,n;

void sort1(int st,int dr)
{
    int i=st,j=dr;
    mid=v[(i+j)/2].a;
    do
    {
        while(v[i].a<mid) i++;
        while(v[j].a>mid) j--;
        if(i<=j)
        {
            aux=v[i];v[i]=v[j];v[j]=aux;
            i++;j--;
        }
    }while(i<=j);
    if(i<dr) sort1(i,dr);
    if(j>st) sort1(st,j);
}

void upheap(int i)
{
    if(i/2 && h[i]>h[i/2])
    {
        swap(h[i],h[i/2]);
        upheap(i/2);
    }
}

void downheap(int i)
{
    if(i*2+1<=k && h[i]<h[i*2+1] && h[i*2+1]>=h[i*2])
    {
        swap(h[i],h[i*2+1]);
        downheap(i*2+1);
    }
    else if(i*2<=k && h[i]<h[i*2] && h[i*2]>=h[i*2+1])
        {
            swap(h[i],h[i*2]);
            downheap(i*2);
        }
}

int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    scanf("%d%d%d",&n,&d,&x);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        if(a<=d)
        {
            v[++nr].a=1+(d-a)/x;
            v[nr].b=b;
        }
    }
    sort1(1,nr);
    v[0].a=0;
    a=0;
    for(i=1;i<=nr;i++)
    {
        a+=v[i].a-v[i-1].a;
        if(a)
        {
            h[++k]=v[i].b;
            upheap(k);
            a--;
        }
        else if(k && h[1]<v[i].b)
            {
                h[1]=v[i].b;
                downheap(1);
            }
    }
    for(i=1;i<=k;i++) s+=h[i];
    printf("%lld",s);
    return 0;
}