Pagini recente » Cod sursa (job #1362051) | Cod sursa (job #1932075) | Cod sursa (job #2645741) | Cod sursa (job #42724) | Cod sursa (job #2415157)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int X,n,L,t,i,h[100001],x,k;
long long maxi,sol;
struct meme{
long long t,l;
}v[100001];
int cmp(meme a,meme b){
if(a.t==b.t)
return a.l>b.l;
return a.t>b.t;
}
void up_heap(int poz){
while(poz/2>=1){
if(v[h[poz]].l>v[h[poz/2]].l)
swap(h[poz],h[poz/2]);
else
return;
poz=poz/2;
}
}
void down_heap(int poz){
while(poz*2<=k){
int st=poz*2;
if(st+1<=k&&v[h[st]].l<v[h[st+1]].l)
st++;
if(v[h[poz]].l<v[h[st]].l)
swap(h[poz],h[st]);
else
return;
poz=st;
}
}
int main()
{ f>>n>>X>>L;
for(i=1;i<=n;i++){
f>>x>>v[i].l;
v[i].t=(X-x)/L+1;
maxi=max(maxi,v[i].t);
}
sort(v+1,v+n+1,cmp);
i=1;k=0;sol=0;
for(t=maxi;t>=1;t--){
while(v[i].t==t){
h[++k]=i;
i++;
up_heap(k);
}
sol+=v[h[1]].l;
swap(h[1],h[k]);
k--;
down_heap(1);
}
g<<sol;
return 0;
}