Mai intai trebuie sa te autentifici.
Cod sursa(job #199824)
Utilizator | Data | 20 iulie 2008 19:41:24 | |
---|---|---|---|
Problema | Lupul Urias si Rau | Scor | 16 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.18 kb |
#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]);
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);
if (l)
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("%lld\n", maxim);
fclose(stdin);
fclose(stdout);
return 0;
}