Pagini recente » Cod sursa (job #3239170) | Cod sursa (job #2591591) | Cod sursa (job #2834449) | Cod sursa (job #2673463) | Cod sursa (job #2788081)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
const int NMAX = 1e5+5;
struct oaie
{
int mutari, lana;
}w[NMAX];
//max_heap
int h[NMAX], nrel;
long long sum = 0;
int root()
{
return h[1];
}
int father(int poz)
{
return poz / 2;
}
int left_son(int poz)
{
return 2 * poz;
}
int right_son(int poz)
{
return 2 * poz + 1;
}
///in jos
void sift(int poz)
{
int max_son;
do
{
max_son = 0;
if(left_son(poz) <= nrel)
{
max_son = left_son(poz);
if(right_son(poz) <= nrel && h[max_son] < h[right_son(poz)])
max_son = right_son(poz);
}
if(max_son == 0)
break ;
if(h[max_son] < h[poz])
max_son = 0;
else swap(h[max_son], h[poz]), poz = max_son;
}while(max_son != 0);
}
///in sus
void percolate(int poz)
{
while(poz > 1 && h[father(poz)] < h[poz]) swap(h[father(poz)], h[poz]), poz = father(poz);
}
void add(int val)
{
h[++nrel] = val;
percolate(nrel);
}
bool comp(oaie a, oaie b)
{
return a.mutari > b.mutari;
}
void del(int poz = 1)
{
if(poz == nrel)
{
--nrel;
return ;
}
swap(h[poz], h[nrel]);
--nrel;
sift(poz);
}
int main()
{
int n, x, l, i, d, maxmut = 0;
fin >> n >> x >> l;
maxmut = x / l;
for(i = 1; i <= n; ++i)
{
fin >> d >> w[i].lana;
w[i].mutari = (x - d) / l;
}
sort(w+1, w+1+n, comp);
int j = 1;
for(i = maxmut; i >= 0; --i)
{
while(j <= n && w[j].mutari == i)
{
add(w[j].lana);
++j;
}
if(nrel > 0)
{
sum += root();
del();
}
}
fout << sum;
return 0;
}