Pagini recente » Cod sursa (job #1125499) | Cod sursa (job #393750) | Cod sursa (job #2568111) | Cod sursa (job #2834398) | Cod sursa (job #2884306)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
const int NMAX = 100000;
int N;
long long X, L, k, in, zmax, inz = 1, S, h[NMAX + 5];
//in este numarul de noduri din heap
struct oi
{
int zile, lana;
} oaie[NMAX + 5];
bool ok(oi a, oi b)
{
if(a.zile == b.zile)
return a.lana > b.lana;
return a.zile > b.zile;
}
int father(int nod)
{
return nod / 2;
}
int left_son(int nod)
{
return nod * 2;
}
int right_son(int nod)
{
return nod * 2 + 1;
}
void percolate(int nod)
{
while(nod > 1 && h[nod] > h[father(nod)])
{
swap(h[nod], h[father(nod)]);
nod = father(nod);
}
}
void sift(int nod)
{
int son = 0;
do
{
son = 0;
if(left_son(nod) <= in)
{
son = left_son(nod);
if(right_son(nod) <= in && h[right_son(nod)] > h[son])
son = right_son(nod);
if(h[son] <= h[nod])
son = 0;
if(son)
{
swap(h[son], h[nod]);
nod = son;
}
}
}while(son);
}
void insrt(int val)
{
h[++in] = val;
percolate(in);
}
void cut(int key)
{
h[key] = h[in];
in--;
sift(key);
}
int main()
{
int x, y;
fin >> N >> X >> L;
for(int i = 1; i <= N; i++)
{
fin >> x >> y;
if(x <= X)
{
oaie[++k].zile = (X - x) / L + 1;
if(oaie[k].zile > zmax)
zmax = oaie[k].zile;
oaie[k].lana = y;
}
}
sort(oaie + 1, oaie + k + 1, ok);
for(int i = zmax; i >= 1; i--)
{
bool ok = 0;
while(oaie[inz].zile == i)
{
insrt(oaie[inz].lana);
inz++, ok = 1;
}
if(in)
{
S += h[1];
cut(1);
}
}
fout << S;
fin.close();
fout.close();
return 0;
}