Pagini recente » Cod sursa (job #518528) | Cod sursa (job #1446303) | Cod sursa (job #170718) | Clasament oni.pre | Cod sursa (job #199881)
Cod sursa(job #199881)
#include <stdio.h>
#include <algorithm>
#define mx 100010
using namespace std;
struct oaie
{
long t, l;
} oi[mx];
long n, x, l, ac, h;
long maxim;
long hp[mx];
inline bool cmp(const oaie &a, const oaie &b)
{
return (a.t < b.t);
}
void heapup(long x)
{
if (hp[x] > hp[x / 2] && x > 1)
{
swap(hp[x],hp[x / 2]);
heapup(x / 2);
}
}
void heapdown(long x)
{
long m = mx - 1;
if (h >= (x << 1))
m = x << 1;
if (h > (x << 1))
if (hp[x << 1] < hp[(x << 1) + 1])
m = (x << 1) + 1;
if (hp[x] < hp[m])
{
swap(hp[x],hp[m]);
heapdown(m);
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%ld %ld %ld", &n, &x, &l);
for (int i = 1; i <= n; i++)
scanf("%ld %ld", &oi[i].t, &oi[i].l);
sort(oi+1,oi+1+n,cmp);
ac = x % l;
for (int i = 1; i <= n && oi[i].t <= x && ac <= x; i++)
{
if (oi[i].t > ac)
{
ac += l;
maxim += hp[1];
hp[1] = oi[i].l;
heapdown(1);
}
else
{
h++;
hp[h] = oi[i].l;
heapup(h);
}
}
while (ac <= x && h)
{
ac += l;
maxim += hp[1];
hp[1] = hp[h];
h--;
heapdown(1);
}
printf("%ld\n", maxim);
fclose(stdin);
fclose(stdout);
return 0;
}