Cod sursa(job #1037496)

Utilizator IonSebastianIon Sebastian IonSebastian Data 20 noiembrie 2013 12:10:56
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
const int N = 100001;
struct oaie {
    int poz;
    int lana;
} v[N];
int h[N], nre;
bool cmp(oaie a, oaie b) {
    return a.poz > b.poz;
}
void afis(int x){
    int j;
    for(j = x; j <= nre; j++){
        out << h[j] << " ";
    }
}
void urca(int poz){
    int aux;
    while(poz > 1 && h[poz] < h[poz/2]){
        aux = h[poz];
        h[poz] = h[poz/2];
        h[poz/2] = aux;
        poz /= 2;
    }
}

void coboara(int poz){
    int aux;
    if(2*poz + 1 <= nre && h[poz] > h[2*poz+1] && h[2*poz+1] <= h[2*poz]){
        aux = h[poz];
        h[poz] = h[2*poz+1];
        h[2*poz+1] = aux;
        coboara(2*poz+1);
    } else {
        if(2*poz <= nre && h[poz] > h[2*poz]){
            aux = h[poz];
            h[poz] = h[2*poz];
            h[2*poz] = aux;
            coboara(2*poz);
        }
    }
}

/*void coboara(int poz){
    int aux, bun;
    while(2*poz <= nre){
        bun = poz;
        if(2*poz <= nre && h[bun] > h[poz*2]){
            bun = 2*poz;
        }
        if(2*poz+1 <= nre && h[bun] > h[poz*2+1]){
            bun = 2*poz + 1;
        }
        if(bun == poz) return;
        aux = h[poz];
        h[poz] = h[bun];
        h[bun] = aux;
        poz = bun;
    }
}*/

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

int main()
{
    int n,x,l, i, timp = 0, lanatot = 0;
    in >> n >> x >> l;
    for(i = 1; i <= n; i++){
        in >> v[i].poz >> v[i].lana;
    }
    sort(v + 1,v + n + 1,cmp);
    for(i = 1; i <= n; i++){
        if(v[i].poz + l*timp <= x){
            adauga(v[i].lana);
            timp++;
        } else {
            if(v[i].lana > h[1]){
                h[1] = v[i].lana;
                coboara(1);
            }
        }
    }
    for(i = 1; i <= nre; i++){
        lanatot += h[i];
    }
    out << lanatot;
    return 0;
}