Pagini recente » Cod sursa (job #2316801) | Cod sursa (job #99011) | Cod sursa (job #3165607) | Cod sursa (job #1861961) | Cod sursa (job #342558)
Cod sursa(job #342558)
#include <fstream.h>
#define MaxN 100009
#define t(x) ((x)/2)
#define fs(x) ((x)*2)
#define fd(x) ((x)*2+1)
long d[MaxN],l[MaxN],T[MaxN],pos[MaxN],heap[MaxN],T_max,X,L,n,s,k,N;
void cit()
{
int i;
ifstream fin("lupu.in");
fin>>n>>X>>L;
for(i=1;i<=n;i++)
{
fin>>d[i]>>l[i];
if(d[i]<=X)
{
T[i]=(X-d[i])/L+1;
if(T[i]>T_max)
T_max=T[i];
}
}
fin.close();
}
void sch(int i,int j)
{
long aux=d[i]; d[i]=d[j]; d[j]=aux;
aux=l[i]; l[i]=l[j]; l[j]=aux;
aux=T[i]; T[i]=T[j]; T[j]=aux;
}
void poz(int li,int ls)
{
long i=0,j=-1,c;
while(li<ls)
{
if(T[li]<T[ls])
{
sch(li,ls);
c=i; i=-j; j=-c;
}
li+=i; ls+=j;
}
k=li;
}
void quick(int li,int ls)
{
if(li<ls)
{
poz(li,ls);
quick(li,k-1);
quick(k+1,ls);
}
}
void swap(int x,int y)
{
int aux=heap[x];
heap[x]=heap[y];
heap[y]=aux;
}
void upheap(int nod)
{
while(nod>1 && heap[t(nod)]<heap[nod])
{
swap(t(nod),nod);
nod=t(nod);
}
}
void insert(int val)
{
N++;
heap[N]=val;
upheap(N);
}
void downheap(int nod)
{
while((fs(nod)<=N && heap[nod]<heap[fs(nod)]) || (fd(nod)<=N && heap[nod]<heap[fd(nod)]))
if(fd(nod)<=N)
{
if(heap[fs(nod)]>heap[fd(nod)])
{
swap(nod,fs(nod));
nod=fs(nod);
}
else
{
swap(nod,fd(nod));
nod=fd(nod);
}
}
else
{
swap(nod,fs(nod));
nod=fs(nod);
}
}
void erase(int nod)
{
swap(nod,N);
N--;
downheap(1);
}
void sol()
{
int i,nr=0,k=1;
for(i=T_max;i>=1;i--)
{
while(T[k]==i && k<=n)
insert(l[k]), k++;
s+=heap[1];
if(N>1)
erase(1);
}
}
void afis()
{
ofstream fout("lupu.out");
fout<<s;
fout.close();
}
int main()
{
cit();
quick(1,n);
sol();
afis();
return 0;
}