Pagini recente » Cod sursa (job #3234325) | Cod sursa (job #2310990) | Cod sursa (job #192707) | Cod sursa (job #2244535) | Cod sursa (job #2067227)
#include <fstream>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
long long n,x,l,i,s;
struct oaie
{
long long d,l;
};
oaie o[100009],aux;
void creareheap();
void down(long long k, long long n);
long long extramax();
void del(long long k, long long &n);
void up(long long k, long long n);
int main()
{
fin>>n>>x>>l;
if(x%l==0)
{
x=x/l;
}
else
{
x=x/l+1;
}
for(i=1;i<=n;i=i+1)
{
fin>>o[i].d>>o[i].l;
if(o[i].d%l==0)
{
o[i].d=o[i].d/l;
}
else
{
o[i].d=o[i].d/l+1;
}
}
creareheap();
for(i=1;i<=n;i=i+1)
{
if(o[i].d>x)
{
del(i,n);
}
}
s=0;
while(n>0)
{
s=s+extramax();
}
fout<<s;
fin.close();
fout.close();
return 0;
}
void creareheap()
{
long long i;
for(i=n/2;i>=1;i=i-1)
{
down(i,n);
}
};
void down(long long k, long long n)
{
long long t,f;
t=k;
f=2*k;
while(f<=n)
{
if(f<n)
{
if(o[f].l<o[f+1].l)
{
f=f+1;
}
}
if(o[t].l<o[f].l)
{
aux=o[t];
o[t]=o[f];
o[f]=aux;
t=f;
f=f*2;
}
else
{
f=n+1;
}
}
};
void up(long long k, long long n)
{
long long t,f;
t=k/2;
f=k;
while(t && o[f].l>o[t].l)
{
aux=o[f];
o[f]=o[t];
o[t]=aux;
f=t;
t=t/2;
}
};
long long extramax()
{
long long v,i,j,d;
v=o[1].l;
d=o[1].d;
j=1;
for(i=n;i>0;i=i-1)
{
if((o[i].d<=x) && (o[i].d>d) || (o[i].d==d && v<o[i].l))
{
v=o[i].l;
d=o[i].d;
j=i;
}
}
o[j]=o[n];
n=n-1;
down(j,n);
x=x-1;
while(n>0 && o[1].d>x)
{
del(1,n);
}
return v;
};
void del(long long k, long long &n)
{
o[k]=o[n];
n=n-1;
if(k>1 && o[k].l>o[k/2].l)
{
up(k,n);
}
else
{
down(k,n);
}
};