Cod sursa(job #1022412)

Utilizator teoionescuIonescu Teodor teoionescu Data 5 noiembrie 2013 13:11:10
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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;
};
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+1].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';
}
int N,X,L;
oaie v[Nmax];
bool cmp(oaie a,oaie b){
    return 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 - v[i].D >=0 ){
            push(v[i]);
            X-=L;
        }
        else{
            push(v[i]);
            pop();
        }
        //H.PRINT();
    }
    long long sum=0;
    for(int i=1;i<=K;i++){
        sum+=H[i].A;
    }
    out<<sum;
    return 0;
}