Pagini recente » Clasament .com | Profil eudanip | preONI 2006 (Runda 1) | Profil eudanip | Cod sursa (job #334706)
Cod sursa(job #334706)
#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
#define mp make_pair
#define nx 100005
#define inf
using namespace std;
vector <int> a[nx];
long long n,x,l,heap[nx],L,T;
long long sol;
void swap (long long &a,long long &b)
{
long long c;
c=a;
a=b;
b=c;
}
void upheap (int x)
{
int aux;
while (x/2 && heap[x]>heap[x/2])
{
swap(heap[x],heap[x/2]);
x/=2;
}
}
void downheap(int x)
{
int y=0;
while (y!=x)
{
y=x;
if (y*2<=L && heap[y*2]>heap[x])
x=y*2;
if (y*2+1<=L && heap[y*2+1]>heap[x])
x=y*2+1;
swap(heap[x],heap[y]);
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%lld%lld%lld",&n,&x,&l);
long long i,p,q,j;
for (i=1;i<=n;++i)
{
scanf("%lld%lld",&p,&q);
if (p<=x)
{
a[(x-p)/l+1].pb(q);
if ((x-p)/l+1>T) T=(x-p)/l+1;
}
}
for (;T>=1;T--)
{
for (j=0;j<a[T].size();++j)
{
heap[++L]=a[T][j];
upheap(L);
}
if (L>0)
{
sol+=heap[1];
heap[1]=heap[L--];
downheap(1);
}
}
printf("%lld\n",sol);
return 0;
}