Pagini recente » Cod sursa (job #1043249) | Cod sursa (job #1767487) | Cod sursa (job #1377351) | Cod sursa (job #1592544) | Cod sursa (job #1465997)
#include <fstream>
#include <algorithm>
#define NMAX 100001
#define MIN -1
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int i, n = 0, x, l, m, timp = 0, ans = 0;
struct oaie
{
int dist, lana;
};
oaie heap[NMAX], a;
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
{
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;
n --;
get_down(k);
}
int main()
{
f >> m >> x >> l;
for (i=1; i<=m; ++i)
{
f >> a.dist >> a.lana;
insert_heap(a);
}
while (n)
{
if (heap[1].dist + timp * l <= x)
{
timp ++;
ans += heap[1].lana;
delete_heap(1);
}
else
delete_heap(1);
}
g << ans << '\n';
return 0;
}