Mai intai trebuie sa te autentifici.
Cod sursa(job #152671)
Utilizator | Data | 9 martie 2008 18:00:55 | |
---|---|---|---|
Problema | Lupul Urias si Rau | Scor | 48 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.02 kb |
#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, tmax,k;
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];
h[p]=0;
p--;
poz=1;
while ((h[poz]<h[poz*2])||(h[poz]<h[poz*2+1]))
{
if (poz*2+1>p)
return;
// mx=maxim(h[poz*2],h[poz*2+1]);
if (h[2*poz]>h[2*poz+1])
{
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+1;
if (d[i]>x)
t[i].t=0;
t[i].p=i;
if (t[i].t>tmax)
tmax=t[i].t;
}
sort(t+1,t+n+1,cmp);
/*for (i=1;i<=n;i++)
printf("%ld %ld \n",t[i].t, z[t[i].p]);*/
j=1;
for (i=tmax;i>=1;i--)
{
while ((t[j].t==i)&&(j<=n))
{
adauga_heap(z[t[j].p]);
++j;
}
/* printf("%d\n",h[1]);
for (k=1;k<=p;k++)
printf("%d ",h[k]);
printf("\n");*/
if (p)
{
s+=h[1];
scoate_heap();
}
}
printf("%lld\n",s);
return 0;
}