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