Pagini recente » Cod sursa (job #2625848) | Cod sursa (job #568075) | Cod sursa (job #2679520) | Cod sursa (job #2531642) | Cod sursa (job #1030476)
#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;
}