Pagini recente » Cod sursa (job #2076316) | Cod sursa (job #2188232) | Cod sursa (job #1725913) | Cod sursa (job #1569032) | Cod sursa (job #340025)
Cod sursa(job #340025)
#include<cstdio>
#define N 100001
#include<algorithm>
using namespace std;
int n,nh,l,x;
long long s,g;
struct lupu{int l,d;}h[N],aux,key;
bool compar(const lupu&a, const lupu&b)
{
return a.l>b.l;
}
void cobor(int k)
{
int fiu;
do
{
fiu=0;
if (2*k<=nh)
{
fiu=2*k;
if (2*k+1<=nh)
if ((h[fiu].l<h[2*k+1].l)||((h[fiu].l==h[2*k+1].l)&&(h[fiu].d<h[2*k+1].d)))
fiu=2*k+1;
if (h[fiu].l<h[k].l)
fiu=0;
}
if (fiu)
{
aux=h[k];
h[k]=h[fiu];
h[fiu]=aux;
k=fiu;
}
}
while(fiu);
}
void urc(int k)
{
key=h[k];
while (k-1&&((key.l>h[k/2].l)||((key.l==h[k/2].l)&&(key.d>h[k/2].d))))
{
h[k]=h[k/2];
k/=2;
}
h[k]=key;
}
void cut(int k)
{
h[k]=h[nh];
--nh;
if (k-1&&((key.l>h[k/2].l)||((key.l==h[k/2].l)&&(key.d>h[k/2].d))))
urc(k);
else
cobor(k);
}
void solve()
{
while (nh)
{
s+=h[1].l;
cut (1);
g+=l;
while (h[1].d+g>x&&nh)
cut(1);
}
}
void citire()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
for (int i=1; i<=n; ++i)
{
int x2,y;
scanf("%d%d",&x2,&y);
if (x2<=x)
{
h[++nh].d=x2;
h[nh].l=y;
}
}
sort (h+1,h+nh+1,compar);
for (int i=nh/2; i; --i)
cobor(i);
}
void afis()
{
/*for (int i=1; i<=n; ++i)
printf("%d %d\n",h[i].d,h[i].l);*/
printf("%lld",s);
}
int main()
{
citire();
solve();
afis();
return 0;
}