Cod sursa(job #1564525)

Utilizator Master011Dragos Martac Master011 Data 9 ianuarie 2016 18:58:59
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<cstdio>
#include<algorithm>
using namespace std;

const int nMax = 100000;
struct oaie{
    int lana, pas;
    bool operator()(const oaie &a, const oaie &b)const
    {
        return a.pas > b.pas;
    }
};

oaie v[nMax + 1];
int h[nMax + 1], cnt, nre = 1;

inline void schimba(int p1, int p2){
    int aux = h[p1];
    h[p1] = h[p2];
    h[p2] = aux;
}

void adauga(int x){
    h[nre++] = x;

    int poz = nre - 1;
    while(poz > 1 && h[poz] > h[poz >> 1]){
        schimba(poz, poz >> 1);
        poz >>= 1;
    }
}

void scoate(int poz){
    schimba(poz, nre - 1);
    nre--;

    int son;
    do{
        son = 0;
        if(poz << 1 < nre){
            son = poz << 1;
            if(son + 1 < nre && h[son + 1] > h[son])
                son++;
            if(h[son] < h[poz])
                son = 0;
            if(son){
                schimba(poz, son);
                poz = son;
            }
        }
    }while(son);
}

int main (){
    FILE *in = fopen("lupu.in","r");
    FILE *out = fopen("lupu.out","w");


    int n, x, l, pm;
    fscanf(in,"%d%d%d",&n,&x,&l);
    for(int i = 0, D, A; i < n ; ++i){
        fscanf(in,"%d%d",&D,&A);
        pm = (x - D) / l;
        if(D <= x){
            v[cnt].pas = pm;
            v[cnt++].lana = A;
        }
    }

    sort(v, v + cnt, oaie());

    int p = v[0].pas, i = 0;
    long long sol = 0;
    while(p >= 0){

        while(v[i].pas >= p && i < cnt){
            adauga(v[i++].lana);
        }

        if(nre > 1)
            sol += (long long) h[1];
        scoate(1);

        p--;
    }

    fprintf(out,"%lld\n",sol);
    return 0;
}