Pagini recente » Cod sursa (job #2366726) | Cod sursa (job #2686183) | Cod sursa (job #288732) | Cod sursa (job #639435) | Cod sursa (job #599898)
Cod sursa(job #599898)
#include<stdio.h>
#define LMAX 100100
#include<algorithm>
struct pozdy
{
int x,cst;
} x[LMAX];
int H[LMAX];
using namespace std;
inline bool comp(pozdy A,pozdy B)
{
return A.x > B.x;
}
void DownHeap(int poz)
{
int fiu,aux;
do
{
fiu=0;
if(2*poz<=H[0])
{
fiu=2*poz;
if(2*poz<H[0] && H[2*poz+1]>H[2*poz])
fiu=2*poz+1;
}
if(H[poz]>=H[fiu])
fiu=0;
if(fiu)
{
aux=H[poz];
H[poz]=H[fiu];
H[fiu]=aux;
poz=fiu;
}
}
while(fiu);
}
void UpHeap(int poz)
{
int aux,fiu=1;
while(poz>1 && fiu)
{
fiu=poz/2;
if(fiu && H[fiu]<H[poz])
{
aux=H[fiu];
H[fiu]=H[poz];
H[poz]=aux;
poz=fiu;
}
else
fiu=0;
}
}
void baga1(int val)
{
int nod,aux;
H[++H[0]]=val; nod=H[0];
while(nod>>1 > 0 && H[nod]>H[nod>>1])
{
aux=H[nod];
H[nod]=H[nod>>1];
H[nod>>1]=aux;
nod=nod>>1;
}
}
void scoate1()
{
int poz=1,fiu,aux;
H[1]=H[H[0]--];
if(!H[0])
return;
do
{
fiu=0;
if(2*poz<=H[0])
{
fiu=2*poz;
if(2*poz<H[0] && H[2*poz+1]>H[2*poz])
fiu=2*poz+1;
}
if(H[poz]>=H[fiu])
fiu=0;
if(fiu)
{
aux=H[poz];
H[poz]=H[fiu];
H[fiu]=aux;
poz=fiu;
}
}
while(fiu);
}
void baga(int val)
{
H[++H[0]]=val;
UpHeap(H[0]);
}
void scoate()
{
H[1]=H[H[0]--];
DownHeap(1);
}
int main()
{
int n,X,L,i,j;
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&X,&L);
for(i=1;i<=n;i++)
{
scanf("%d%d",&x[i].x,&x[i].cst);
x[i].x=(X-x[i].x)/L+1;
if(x[i].x<0)
i--,n--;
}
sort(x+1,x+n+1,comp);
long long s=0;
for(i=1;i<=n;i++)
{
baga1(x[i].cst);
if(x[i].x!=x[i+1].x)
for(j=1;j<=x[i].x-x[i+1].x;j++)
{
if(H[0]==0)
break;
s+=H[1];
scoate1();
}
}
printf("%lld\n",s);
return 0;
}