Pagini recente » Cod sursa (job #2100331) | Cod sursa (job #2528343) | Cod sursa (job #39069) | Cod sursa (job #1790769) | Cod sursa (job #2912176)
#include <fstream>
#include <algorithm>
#define DIM 100001
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int n,x,l,d,a,k,i,j,tmax,t,nr,h[DIM];
long long sol;
struct oaie {
int t,l;
}v[DIM];
bool cmp(oaie a,oaie b) {
if (a.t==b.t)
return a.l>b.l;
return a.t>b.t;
}
void upHeap(int k) {
while (k>1 && h[k]>h[k/2]) {
swap(h[k],h[k/2]);
k/=2;
}
}
void downHeap(int k) {
while (2*k<=nr) {
int p=2*k;
if (p+1<=nr && h[p+1]>h[p])
p++;
if (h[p]>h[k]) {
swap(h[p],h[k]);
k=p;
}
else
break;
}
}
int main() {
fin>>n>>x>>l;
for (i=1;i<=n;i++) {
fin>>d>>a;
if (d<=x) {
v[++k]={(x-d)/l+1,a};
tmax=max(tmax,v[k].t);
}
}
sort(v+1,v+k+1,cmp);
j=1;
for (i=tmax;i>=1;i--) {
while (j<=k && v[j].t==i) {
h[++nr]=v[j].l;
upHeap(nr);
j++;
}
if (nr!=0) {
sol+=h[1];
h[1]=h[nr--];
downHeap(1);
}
}
fout<<sol;
return 0;
}