Pagini recente » Cod sursa (job #937036) | Cod sursa (job #979153) | Cod sursa (job #554475) | Borderou de evaluare (job #1508889) | Cod sursa (job #2415187)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
long long X,n,L,t,i,h[100005],x,k,maxi,sol;
struct meme{
int t,l;
}v[100005];
class compare{
public:
bool operator ()(int a, int b){
return a<b;
}
};
priority_queue <int, vector<int>, compare> q;
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,1ll*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&&i<=n){
/* h[++k]=i;
up_heap(k);*/
q.push(v[i].l);
i++;
}
if(!q.empty()){
/* sol+=v[h[1]].l;
swap(h[1],h[k]);
k--;
down_heap(1);*/
sol+=q.top();
q.pop();
}
}
g<<sol;
return 0;
}