Mai intai trebuie sa te autentifici.
Cod sursa(job #214948)
Utilizator | Data | 16 octombrie 2008 23:21:15 | |
---|---|---|---|
Problema | Lupul Urias si Rau | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.21 kb |
#include <stdio.h>
#include <algorithm>
#define mx 100010
using namespace std;
pair <int, int> oi[mx];
long n, x, l, ac, h;
long long maxim;
long hp[mx];
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].first, &oi[i].second);
sort(oi+1,oi+1+n);
ac = x % l;
for (int i = 1; i <= n && oi[i].first <= x && ac <= x; i++)
{
if (oi[i].first > ac)
{
if (h)
ac += l;
maxim += (long long) hp[1];
if (!h)
h++;
hp[1] = oi[i].second;
heapdown(1);
}
else
{
h++;
hp[h] = oi[i].second;
heapup(h);
}
}
while (ac <= x && h)
{
ac += l;
maxim += (long long) hp[1];
hp[1] = hp[h];
h--;
heapdown(1);
}
printf("%lld\n", maxim);
fclose(stdin);
fclose(stdout);
return 0;
}