Pagini recente » Istoria paginii runda/uvs_training_runda.1 | Istoria paginii runda/geometrie01 | Cod sursa (job #2000239) | Istoria paginii runda/fmi_bis | Cod sursa (job #199872)
Cod sursa(job #199872)
#include <stdio.h>
#include <algorithm>
#define mx 100010
using namespace std;
struct oaie
{
long t, l;
} oi[mx];
long n, x, l, ac;
long 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 maxim = mx - 1;
if (hp[0] >= (x << 1))
maxim = x << 1;
if (hp[0] > (x << 1))
if (hp[x << 1] < hp[(x << 1) + 1])
maxim = (x << 1) + 1;
if (hp[x] < hp[maxim])
{
swap(hp[x],hp[maxim]);
heapdown(maxim);
}
}
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 += (long long) hp[1];
hp[1] = oi[i].l;
heapdown(1);
}
else
{
hp[0]++;
hp[hp[0]] = oi[i].l;
heapup(hp[0]);
}
}
while (ac <= x && hp[0])
{
ac += l;
maxim += (long long) hp[1];
hp[1] = hp[hp[0]];
hp[0]--;
heapdown(1);
}
printf("%lld\n", maxim);
fclose(stdin);
fclose(stdout);
return 0;
}