Pagini recente » Cod sursa (job #1643141) | Cod sursa (job #329335) | Cod sursa (job #893011) | Cod sursa (job #317692) | Cod sursa (job #1847322)
#include <cstdio>
#include <algorithm>
#include<queue>
using namespace std;
struct oita {
int lana,strat;
};
oita oaie[100005];
int nh, n,i,k,l,distanta,lana,nr;
long long totalLana;
int heap[100005];
bool cmp(oita a,oita b) {
return (a.strat>b.strat);
}
void up(int k){
while(k/2>0 && heap[k/2]<heap[k]){
swap(heap[k],heap[k/2]);
k=k/2;
}
}
void down(int k){
int pfiu;
while(2*k<=nh){
pfiu=-1;
if(heap[k]<heap[2*k])
pfiu=2*k;
if(2*k+1<=nh && heap[k]<heap[2*k+1] && heap[2*k+1]>heap[pfiu])
pfiu=2*k+1;
if(pfiu!=-1){
swap(heap[k],heap[pfiu]);
k=pfiu;
}
else
return;
}
}
int main() {
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d %d %d",&n,&l,&k);
for (i=1;i<=n;i++) {
scanf("%d %d",&distanta,&lana);
if(distanta<=l){
nr++;
oaie[nr].lana=lana;
oaie[nr].strat = (l-distanta)/k;
}
}
n=nr;
sort(oaie+1,oaie+n+1,cmp);
i=1;
for(int d=l/k;d>=0;d--){//
//pun oile care apartin stratului d in heap
while(i<=n && oaie[i].strat==d){
heap[++nh]=oaie[i].lana;up(nh);
i++;
}
if(nh>0){
totalLana+=heap[1];
heap[1]=heap[nh--];
down(1);
}
}
printf("%lld\n",totalLana);
return 0;
}