Pagini recente » Clasament snyc.1 | Istoria paginii utilizator/arctos | Cod sursa (job #1291779) | Istoria paginii runda/de_ce_sa_ne_certam_iubi | Cod sursa (job #199820)
Cod sursa(job #199820)
#include <stdio.h>
#include <algorithm>
#define mx 100010
using namespace std;
struct oaie
{
long long t, l;
} oi[mx];
long long n, x, l, 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]);
if (x > 1)
heapup(x / 2);
}
}
void heapdown(long x)
{
int maxim = 0;
if (hp[0] >= (x << 1))
maxim = x << 1;
if (hp[0] > (x << 1) && 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);
int ac = x % l;
for (int i = 1; i <= n; 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]);
}
}
maxim += (long long) hp[1];
printf("%ld\n", maxim);
fclose(stdin);
fclose(stdout);
return 0;
}