Cod sursa(job #1665134)

Utilizator antanaAntonia Boca antana Data 26 martie 2016 16:41:19
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <cstdio>
#include<algorithm>
#define MAX 100000
using namespace std;
int n, x, m;
long long cf, l, tot;
struct oite_vesele{
    int dist, cost;
}; oite_vesele v[MAX+1];
int heap[MAX+1];
bool cresc(oite_vesele a, oite_vesele b)
{
    return (a.dist<b.dist);
}
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(father(x)>0&&(f))
    {
        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(son_left(x)<=m&&(f))
    {
        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, f=1;
    scanf("%d%d%lld", &n, &x, &l);
    for(i=1;i<=n;i++)
        scanf("%d%d", &v[i].dist, &v[i].cost);
    sort(v+1, v+n+1, cresc);
    i=1;
    while((f)&&cf<=x)
    {
        while(m>0&&v[heap[1]].dist+cf>x)
            delete1();
        if(m==0)
            f=0;
        while(i<=n&&v[i].dist+cf<=x){
            add(i);
            i++;
            f=1;
        }
        if(m!=0){
        tot+=v[heap[1]].cost;
        delete1();
        cf+=l;
        }
    }
    printf("%lld", tot);
    return 0;
}