Pagini recente » Cod sursa (job #99576) | Cod sursa (job #70088) | Cod sursa (job #2639102) | Cod sursa (job #759889) | Cod sursa (job #1847305)
#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;
oaie[++n].strat=-1;
sort(oaie+1,oaie+n+1,cmp);
heap[++nh]=oaie[1].lana;
for (i=2;i<=n;i++) {
if (oaie[i].strat != oaie[i-1].strat)
{
int x = oaie[i-1].strat - oaie[i].strat;
for (int j=1;j<=x;j++) {
if (nh>0){
totalLana += heap[1];
heap[1]=heap[nh--];
if(nh>0)
down(1);
}
}
}
heap[++nh]=oaie[i].lana;
up(nh);
}
printf("%lld\n",totalLana);
return 0;
}