Pagini recente » Cod sursa (job #805001) | Cod sursa (job #3288890) | Cod sursa (job #3165692) | Cod sursa (job #1005154) | Cod sursa (job #1463)
Cod sursa(job #1463)
#include <stdio.h>
#define NMAX 100001
#define DAD(x) (x/2)
#define ST(x) (2*x)
#define DR(x) (2*x+1)
#define INF "lupu.in"
#define OUF "lupu.out"
unsigned long t[NMAX],a[NMAX];
struct heap
{
unsigned long h[NMAX],dim;
void init(unsigned long key);
void insert(unsigned long key);
void rebuild(unsigned long i);
unsigned long max();
}m;
void heap::init(unsigned long key)
{
dim=1;
h[dim]=key;
}
void heap::insert(unsigned long key)
{
dim++;
register unsigned long i;
i=dim;
while(i>1&&h[DAD(i)]<key)
{
h[i]=h[DAD(i)];
i=DAD(i);
}
h[i]=key;
}
void heap::rebuild(unsigned long i)
{
unsigned long l,r,maxi;
l=ST(i);
r=DR(i);
if(l<=dim&&h[l]>h[i]) maxi=l;
else maxi=i;
if(r<=dim&&h[r]>h[maxi]) maxi=r;
if(maxi!=i)
{
l=h[i];h[i]=h[maxi];h[maxi]=l;
rebuild(maxi);
}
}
unsigned long heap::max()
{
unsigned long maxi;
if(dim>0)
{
maxi=h[1];
h[1]=h[dim];dim--;
rebuild(1);
}
else maxi=0;
return maxi;
}
void qsort(unsigned long st,unsigned long dr)
{
unsigned long i, j,aux, piv;
i=st; j=dr;piv=t[i];
do{
while ( t [ i ] > piv ) i++;
while ( t [ j ] < piv) j--;
if(i<=j)
{//interschimbi
aux=a[i]; a[i]=a[j]; a[j]=aux;
aux=t[i]; t[i]=t[j]; t[j]=aux;
i++ ; j--;
}
}while(i<=j);
if(i<dr)qsort(i,dr);
if(j>st)qsort(st,j);
}
main()
{
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
unsigned long n,x,l,v=0,tmax=0,p=0;
register unsigned long i,j;
unsigned long long s=0;
fscanf(in,"%ld %ld %ld",&n,&x,&l);
for(i=1;i<=n;i++)
{
fscanf(in,"%ld %ld",&v,a+i);
t[i]=(v<=x)?((x-v)/l+1):(0);
}
qsort(1,n);
m.init(a[1]);tmax=t[1];
i=2;
while(t[i]==tmax){ m.insert(a[i]);i++;}
s+=m.max();tmax--;
while(tmax>0)
{
if(tmax==t[i])
{
x=t[i];
while(t[i]==x&&i<n)
{
m.insert(a[i]);
i++;
}
}
s+=m.max();
tmax--;
}
fprintf(out,"%lld ",s);
fclose(in);fclose(out);
}