Cod sursa(job #1037439)

Utilizator IonSebastianIon Sebastian IonSebastian Data 20 noiembrie 2013 11:23:21
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
const int N = 100001;
struct oaie {
    long long poz;
    long long lana;
} v[N];
long long h[N], nre;
bool cmp(oaie a, oaie b) {
    return a.poz > b.poz;
}
void urca(long long poz){
    long long aux;
    while(poz!= 1 && h[poz] < h[poz/2]){
        aux = h[poz];
        h[poz] = h[poz/2];
        h[poz/2] = aux;
    }
}
void coboara(int poz){
    long long aux;
    while(poz != nre && (h[poz] > h[poz*2] || h[poz] > h[poz*2+1])){
        if(h[poz] > h[poz*2] && 2*poz <= nre){
            aux = h[poz*2];
            h[poz*2] = h[poz];
            h[poz] = aux;
            poz = 2*poz;
        } else {
            if(h[2*poz+1] <= nre){
                aux = h[poz*2+1];
                h[poz*2+1] = h[poz];
                h[poz] = aux;
                poz = 2*poz+1;
            }
        }
    }
}
void adauga(long long x){
    h[++nre] = x;
    urca(nre);
}
void sterge(long long poz){
    int aux;
    aux = h[poz];
    h[poz] = h[nre];
    h[nre] = aux;
    nre--;
    urca(poz);
    coboara(poz);
}
int main()
{
    long long 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++;
            lanatot += v[i].lana;
        } else {
            if(v[i].lana > h[1]){
                lanatot += v[i].lana - h[1];
                adauga(v[i].lana);
                sterge(1);
            }
        }
    }
    /*for(i = 1; i <= nre; i++){
        lanatot += h[i];
    }*/
    out << lanatot;
    return 0;
}