Pagini recente » Cod sursa (job #1595599) | Cod sursa (job #1326772) | Cod sursa (job #2816890) | Cod sursa (job #1684123) | Cod sursa (job #1259121)
#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 nr,i,j,n,X,L;
long long sol=0;
bool comp(const oaie &A, const oaie &B){
if(A.timp==B.timp) return (A.profit>B.profit);
else return (A.timp>B.timp);
}
int main(){
fi>>n>>X>>L;
for(i=1;i<=n;i++){
++nr;
fi>>a[nr].dist>>a[nr].profit;
a[nr].timp=(X-a[i].dist)/L;
if(a[nr].dist>X) --nr;
}
sort(a+1,a+nr+1,comp);
for(i=1;i<=nr;i++)
{
h.adauga(a[i].profit);
for(j=i+1; j<=nr && a[i].timp==a[j].timp; ++j) h.adauga(a[j].profit);
i=j-1;
sol+=1LL*h.maxim();
h.sterge(1);
}
fo<<sol;
fi.close();
fo.close();
return 0;
}