Pagini recente » Cod sursa (job #291711) | Cod sursa (job #936810) | Cod sursa (job #2096179) | Cod sursa (job #1452217) | Cod sursa (job #645399)
Cod sursa(job #645399)
#include <cstdio>
#include <algorithm>
using namespace std;
int n,l,x,h[100001],nr;
long long s;
struct pct
{
int dist,puf;
};
pct v[100001];
bool cmp(pct x,pct y)
{
if (x.dist <= y.dist)
return false;
return true;
}
void urca(int p)
{
int aux;
if (p>=2 && h[p] <= h[p/2])
{
aux=h[p/2];
h[p/2]=h[p];
h[p]=aux;
urca(p/2);
}
}
void coboara(int p)
{
int pmax=p,aux;
if (2*p<= nr && h[2*p] < h[pmax])
pmax=2*p;
if (2*p+1<= nr && h[2*p+1] < h[pmax])
pmax=2*p+1;
if (pmax != p)
{
aux=h[pmax];
h[pmax]=h[p];
h[p]=aux;
coboara(pmax);
}
}
int main()
{
int i;
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",&v[i].dist,&v[i].puf);
sort(&v[1],&v[n+1],cmp);
for (i=1; i<=n; ++i)
{
if (v[i].dist <= x)
{
h[++nr]=v[i].puf;
urca(nr);
x -= l;
}
else
if (nr>=1 && v[i].puf > h[1])
{
h[1]=v[i].puf;
coboara(1);
}
}
for (i=1; i<=nr; ++i)
s+=h[i];
printf("%lld\n",s);
return 0;
}