Cod sursa(job #1234928)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 28 septembrie 2014 12:59:08
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <algorithm>
#define f first
#define s second
#define Nmax 100000+10

using namespace std;

pair <int,int> oaie[Nmax];
int n,x,l,d,e,i,Max;
int a[Nmax];
long long SOL;

inline void heap_up(int x)
{
    if (x<=1) return;
    int t=x/2;
    if (a[x]>a[t])
    {
        swap(a[x],a[t]);
        heap_up(t);
    }
}

inline void heap_down(int r,int k)
{
    int st,dr,i;
    if (2*r<=k)
    {
        st=a[2*r];
        if (2*r+1<=k) dr=a[2*r+1];
        else dr=st-1;

        if (st>dr) i=2*r;
        else i=2*r+1;

        if (a[r]<a[i])
        {
            swap(a[r],a[i]);
            heap_down(i,k);
        }

    }
}


int main()
{
    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", &d, &oaie[++e].s);
        if (d>x)
        {
            e--;
            continue;
        }
        oaie[e].f=(x-d)/l;
        if (oaie[e].f>Max) Max=oaie[e].f;
    }

    sort(oaie+1,oaie+e+1);
    int p=e;
    for (i=Max; i>=0; --i)
    {
        while (oaie[p].f==i && p>0)
        {
            a[++a[0]]=oaie[p].s;
            heap_up(a[0]);
            --p;
        }

        if (a[0]>0)
        {
            SOL+=1LL*a[1];
            swap(a[1],a[a[0]]);
            a[0]--;
            heap_down(1,a[0]);
        }
    }

    printf("%lld\n", SOL);

    return 0;
}