Cod sursa(job #1037478)

Utilizator IonSebastianIon Sebastian IonSebastian Data 20 noiembrie 2013 11:59:18
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 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, bun;
    while(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;
}