Pagini recente » Cod sursa (job #1617215) | Cod sursa (job #1342852) | Cod sursa (job #1336416) | Cod sursa (job #691696) | Cod sursa (job #1466021)
#include <fstream>
#include <algorithm>
#define NMAX 200005
#define MIN -1
#define INF (1 << 31) - 1
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int i, n = 0;
long long ans = 0, x, l, m, timp = 0, tmax = -1;
bool visited[NMAX];
struct oaie
{
int dist, lana;
};
oaie heap[NMAX], a[NMAX];
int father(int x)
{
return x/2;
}
int left_son(int x)
{
return 2*x;
}
int right_son(int x)
{
return 2*x + 1;
}
void get_down(int k)
{
int aux;
do
{
aux = 0;
if (left_son(k) <= n)
aux = left_son(k);
if (right_son(k) <= n && heap[right_son(k)].lana > heap[aux].lana)
aux = right_son(k);
if (heap[right_son(k)].lana < heap[k].lana && heap[left_son(k)].lana < heap[k].lana)
aux = 0;
if (aux)
{
swap(heap[aux], heap[k]);
k = aux;
}
}while (aux);
}
void get_up(int k)
{
while (k > 1 && heap[k].lana > heap[father(k)].lana)
{
swap(heap[k], heap[father(k)]);
k = father(k);
}
}
void insert_heap(oaie x)
{
heap[++n] = x;
get_up(n);
}
void delete_heap(int k)
{
heap[k] = heap[n];
// heap[n].lana = MIN;
// heap[n].dist = INF;
n --;
get_down(k);
}
int main()
{
f >> m >> x >> l;
for (i=1; i<=m; ++i)
{
f >> a[i].dist >> a[i].lana;
tmax = max(tmax, (x - a[i].dist) / l);
}
do
{
tmax = -1;
n = 0;
for (i=1; i<=m; ++i)
if (a[i].dist + timp * l > x - l && a[i].dist + timp * l <= x)
insert_heap(a[i]);
if (n)
ans += (long long) heap[1].lana, timp++;
}
while (n);
g << ans << '\n';
return 0;
}