Cod sursa(job #1665189)

Utilizator antanaAntonia Boca antana Data 26 martie 2016 17:36:49
Problema Lupul Urias si Rau Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#include<algorithm>
#define MAX 100000
using namespace std;
int n, x, m;
long long cf, l, tot;
struct oite_vesele{
    int maxp, cost;
}; oite_vesele v[MAX+1];
int heap[MAX+1];
bool cresc(oite_vesele a, oite_vesele b)
{
    return (a.maxp>b.maxp);
}
inline int father(int x){ return x/2;};
inline int son_left(int x){ return x*2;};
inline int son_right(int x){ return x*2+1;};
inline void swap1(int a, int b)
{
    int aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
}
inline void up(int x)
{
    int p, f=1;
    while((f)&&father(x)>0)
    {
        f=0;
        p=father(x);
        if(v[heap[p]].cost<v[heap[x]].cost)
        {
            swap1(p, x);
            f=1;
        }
        x=p;
    }
}
inline void down(int x)
{
    int p, q, f=1;
    while((f)&&son_left(x)<=m)
    {
        f=0;
        p=son_left(x);
        q=son_right(x);
        if(v[heap[p]].cost<v[heap[q]].cost)
            p=q;
        if(v[heap[p]].cost>v[heap[x]].cost)
        {
            swap1(p, x);
            f=1;
        }
        x=p;
    }
}
inline void add(int x)
{
    heap[++m]=x;
    up(m);
}
inline void delete1()
{
    swap1(1, m);
    m--;
    down(1);
}
int main()
{
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);
    int i, dist, m1=0, val, pasmax=-1, j;
    scanf("%d%d%lld", &n, &x, &l);
    for(i=1;i<=n;i++){
        scanf("%d%d", &dist, &val);
        if(dist<=x)
        {
            v[++m1].cost=val;
            v[m1].maxp=(x-dist)/l;
            if(v[m1].maxp>pasmax)
                pasmax=v[m1].maxp;
        }
    }
    sort(v+1, v+m1+1, cresc);
    j=1;
    for(i=pasmax;i>=0;i--)
    {
        while(v[j].maxp>=i&&j<=m1)
        {
            add(j);
            j++;
        }
        if(m>0){
            tot+=v[heap[1]].cost;
            delete1();
        }
    }
    printf("%lld", tot);
    return 0;
}