Pagini recente » Cod sursa (job #2845680) | Cod sursa (job #2567313) | Cod sursa (job #58977) | Cod sursa (job #2944251) | Cod sursa (job #910)
Cod sursa(job #910)
#include <stdio.h>
#include <algorithm>
using namespace std;
struct str
{
int val, d;
};
void maxheapify(int* v,int pos);
void buildmaxheap(int* v);
bool cmp(str one, str two);
int n, x, l, heap[100001], heapsize, sol;
str a[100001];
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int i, tmp;
scanf("%d%d%d",&n,&x,&l);
for (i = 1; i <= n; ++i)
{
scanf("%d%d",&a[i].d,&a[i].val);
}
sort(a + 1, a + n + 1, cmp);
tmp = 0;
for (i = 1; i <= n && tmp <= x; ++i)
{
while(a[i].d <= tmp && i <= n)
{
heap[++heapsize] = a[i].val;
++i;
}
buildmaxheap(heap);
if(heapsize > 0)
{
sol += heap[1];
heap[1] = heap[heapsize];
--heapsize;
maxheapify(heap,1);
}
--i;
tmp += l;
}
printf("%d\n",sol);
return 0;
}
void maxheapify(int* v,int pos)
{
int l, r, largest = pos, temp ;
l = 2 * pos;
r = 2 * pos + 1;
if(l <= heapsize && v[l] > v[largest])
largest = l;
if(r <= heapsize && v[r] > v[largest])
largest = r;
if(largest != pos)
{
temp = v[pos];
v[pos] = v[largest];
v[largest] = temp;
maxheapify(v,largest);
}
}
void buildmaxheap(int* v)
{
int i;
for (i = heapsize/2; i > 0; --i)
{
maxheapify(v,i);
}
}
bool cmp(str one, str two)
{
return one.d < two.d;
}