Cod sursa(job #1030476)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 15 noiembrie 2013 16:26:23
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;

struct oaie {
    int dist;
    int lana;
    };
oaie v[100005],heap[100005];
int n,x,l,k;
long long sum;

bool cmp(oaie a,oaie b){
    return a.dist > b.dist;
}

void citire () {

    ifstream in("lupu.in");

    in>>n>>x>>l;
    for(int i=1;i<=n;i++){
        in>>v[i].dist>>v[i].lana;
    }
    sort(v+1,v+n+1,cmp);
    in.close();
}

void downheap (int i) {

    if(2*i+1<=k && heap[i].lana > heap[2*i+1].lana && heap[2*i+1].lana <= heap[2*i].lana){
        swap(heap[2*i+1],heap[i]);
        downheap(2*i+1);
    }
    else if(2*i<=k && heap[i].lana > heap[2*i].lana){
        swap(heap[2*i],heap[i]);
        downheap(2*i);
    }

}

void upheap (int i) {

    if(i/2>=1 && heap[i].lana < heap[i/2].lana) {
        swap(heap[i],heap[i/2]);
        upheap(i/2);
    }


}
void pop () {

    swap(heap[1],heap[k]);
    k--;
    downheap(1);

}

void push (oaie x) {

    heap[++k]=x;
    upheap(k);

}

void solve () {

    int i ;
    for(i=1;i<=n;i++) {

        if (x-v[i].dist>=0) {
           push(v[i]);
            x-=l;
        }
        else {
            push(v[i]);
            pop();
        }

    }

    for(int i=1;i<=k;i++)
        sum+=heap[i].lana;

}

void afisare() {

    ofstream out("lupu.out");
    out<<sum<<'\n';
    out.close();

}

int main() {

    citire();
    solve();
    afisare();

    return 0;

}