Pagini recente » Cod sursa (job #1920849) | Cod sursa (job #1321941) | Cod sursa (job #1256292) | Cod sursa (job #1503121) | Cod sursa (job #1259157)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fi("lupu.in");
ofstream fo("lupu.out");
class Max_Heap{
private:
int h[100005];
int heapsize;
void coboara(int k);
void urca(int k);
public:
Max_Heap();
void adauga(int k);
void sterge(int k);
int maxim();
int heap_size();
};
void Max_Heap::coboara(int k){
bool ok=1;
int nod;
while(ok)
{
ok=0;
if(2*k<=heapsize){
nod=2*k;
if(2*k+1<=heapsize && h[2*k+1]>h[nod]) nod=2*k+1;
if(h[nod]>h[k]){
ok=1;
swap(h[nod],h[k]);
k=nod;
}
}
}
}
void Max_Heap::urca(int k){
while(k>1 && h[k]>h[k>>1]){
swap(h[k],h[k/2]);
k>>=1;
}
}
Max_Heap::Max_Heap(){
heapsize=0;
}
void Max_Heap::adauga(int x){
h[++heapsize]=x;
urca(heapsize);
}
void Max_Heap::sterge(int k){
h[k]=h[heapsize--];
urca(k);
coboara(k);
}
int Max_Heap::maxim(){
return h[1];
}
int Max_Heap::heap_size(){
return heapsize;
}
struct oaie{
int dist;
int profit;
int timp;
};
const int MAX_N = 100005;
Max_Heap h;
oaie a[MAX_N];
int timp,tmax,i,j,n,nr,X,L;
long long sol=0;
bool comp(const oaie &A, const oaie &B){
return (A.timp>B.timp);
}
int main(){
fi>>n>>X>>L;
for(i=1;i<=n;i++){
int distanta;
int profitul;
fi>>distanta>>profitul;
if(distanta<=X){
++nr;
a[nr].dist=distanta;
a[nr].profit=profitul;
a[nr].timp=(X-a[i].dist)/L;
}
}
sort(a+1,a+nr+1,comp);
tmax=a[1].timp;
for(timp=tmax,j=1; timp>=0; --timp)
{
for(; j<=nr && timp==a[j].timp; ++j) h.adauga(a[j].profit);
if(h.heap_size()){
sol+=1LL*h.maxim();
h.sterge(1);
}
}
fo<<sol;
fi.close();
fo.close();
return 0;
}