Pagini recente » Cod sursa (job #1532277) | Cod sursa (job #2235521) | Cod sursa (job #3178631) | Cod sursa (job #1344972) | Cod sursa (job #152645)
Cod sursa(job #152645)
#include <cstdio>
#include <algorithm>
using namespace std;
struct oaie{long t; long p;};
long n,i,j,x,l,d[100100], z[10010l], h[200100],p;
oaie t[100100];
long long s;
bool cmp(oaie a, oaie b)
{
if (a.t>b.t)
return true;
else
return false;
}
void adauga_heap( long x)
{
long poz,aux;
p++;
h[p]=x;
poz=p;
while ((h[poz]>h[poz/2])&&(poz>1))
{
aux=h[poz];
h[poz]=h[poz/2];
h[poz/2]=aux;
poz/=2;
}
}
long long maxim( long a, long b)
{
if (a>b)
return a;
else
return b;
}
void scoate_heap()
{
long poz,mx,aux;
h[1]=h[p];
p--;
poz=1;
while ((h[poz]<maxim(h[poz*2],h[poz*2+1])))
{
mx=maxim(h[poz*2],h[poz*2+1]);
if (mx==h[2*poz])
{
aux=h[poz];
h[poz]=h[2*poz];
h[2*poz]=aux;
poz*=2;
}
else
{
aux=h[poz];
h[poz]=h[2*poz+1];
h[2*poz+1]=aux;
poz=poz*2+1;
}
}
}
int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%ld%ld%ld",&n,&x,&l);
for (i=1;i<=n;++i)
{
scanf("%ld%ld",&d[i],&z[i]);
t[i].t=(x-d[i])/l;
if (d[i]>x)
t[i].t=-1;
t[i].p=i;
}
sort(t+1,t+n+1,cmp);
/*for (i=1;i<=n;i++)
printf("%ld %ld \n",t[i].t, z[t[i].p]);*/
i=1;
while (i<=n)
{
j=i;
while ((t[j].t==t[i].t)&&(j<=n))
{
if (t[j].t>=0)
adauga_heap(z[t[j].p]);
++j;
}
// printf("%d\n",h[1]);
if (t[j-1].t>=0)
{
s+=h[1];
scoate_heap();
}
i=j;
}
for (i=t[n].t-1;i>=0;i--)
{
s+=h[1];
scoate_heap();
}
printf("%lld\n",s);
return 0;
}