Cod sursa(job #1022390)

Utilizator teoionescuIonescu Teodor teoionescu Data 5 noiembrie 2013 12:48:07
Problema Lupul Urias si Rau Scor 36
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 Nmax = 100005;
struct oaie{
    int D,A;
};
struct Heap{
    oaie H[Nmax]; int K;
    void upheap(int i){
        if(i/2>=1 && H[i].A < H[i/2].A){
            swap(H[i],H[i/2]);
            upheap(i/2);
        }
    }
    void downheap(int i){
        if(2*i+1<=K && H[i].A > H[2*i].A && H[2*i+1].A <= H[2*i].A){
            swap(H[2*i+1],H[i]);
            downheap(2*i+1);
        }
        else if(2*i<=K && H[i].A > H[2*i].A){
            swap(H[2*i],H[i]);
            downheap(2*i);
        }
    }
    void push(oaie x){
        H[++K]=x;
        upheap(K);
    }
    void pop(){
        swap(H[1],H[K]);
        K--;
        downheap(1);
    }
    void PRINT(){
        for(int i=1;i<=K;i++) out<<H[i].D<<' '; out<<'\n';
        for(int i=1;i<=K;i++) out<<H[i].A<<' '; out<<'\n';
        out<<'\n';
    }
} H;
int N,X,L;
oaie v[Nmax];
bool cmp(oaie a,oaie b){
    return ( a.D==b.D ? a.A > b.A : a.D > b.D );
}
int main(){
    in>>N>>X>>L;
    for(int i=1;i<=N;i++){
        in>>v[i].D>>v[i].A;
    }
    sort(v+1,v+N+1,cmp);
    int i;
    for(i=1; i<=N && v[i].D > X ;i++);
    for(;i<=N;i++){
        if ( X - H.K*L - v[i].D >=0 ){
            H.push(v[i]);
        }
        else{
            H.push(v[i]);
            H.pop();
        }
        //H.PRINT();
    }
    long long sum=0;
    for(int i=1;i<=H.K;i++){
        sum+=H.H[i].A;
    }
    out<<sum;
    return 0;
}