Pagini recente » Cod sursa (job #3239334) | Cod sursa (job #1399129)
#include <fstream>
#include <vector>
#define father(x) x / 2
#define left_son(x) 2 * x
#define right_son(x) 2 * x + 1
using namespace std;
fstream f("lupu.in", ios::in);
fstream g("lupu.out", ios::out);
const int nmax = 100010;
int a[nmax], t[nmax], h[nmax], n, d, l, tmax, i, j, nr;
long long sum;
void read()
{
int pas, dist, lana;
f >> n >> d >> l;
tmax = 0;
for (i = 1; i <= n; i++)
{
f >> dist >> lana;
pas = 1 + (d - dist)/l;
a[i] = lana;
t[i] = pas;
if (pas > tmax) tmax = pas;
}
}
void swap(int x, int y)
{
int aux = h[x];
h[x] = h[y];
h[y] = aux;
}
void up(int nod)
{
while ((nod > 1) && (h[nod] > h[father(nod)]))
{
swap(nod, father(nod));
nod = father(nod);
}
}
void down(int nod)
{
int ch = 1, son;
while ((left_son(nod) <= nr) && (ch))
{
ch = 0;
son = left_son(nod);
if ((right_son(nod) <= nr) && (h[right_son(nod)] > h[son])) son = right_son(nod);
if (h[son] > h[nod])
{
ch = 1;
swap(nod, son);
nod = son;
}
}
}
void solve()
{
int poz = 1;
for (i = tmax; i >= 1; i--)
{
while ((t[poz] == i) && (poz < n))
{
nr++;
h[nr] = a[poz];
up(nr);
poz++;
}
if (nr)
{
sum += h[1];
h[1] = h[nr];
nr--;
down(1);
}
}
}
void quickSort(int li, int ls)
{
int i = li, j = ls, aux;
int mij = t[(i + j) / 2];
while (i <= j)
{
while (t[i] > mij) i++;
while (t[j] < mij) j--;
if (i <= j)
{
aux = t[i];
t[i] = t[j];
t[j] = aux;
aux = a[i];
a[i] = a[j];
a[j] = aux;
i++; j--;
}
}
if (li < j) quickSort(li, j);
if (i < ls) quickSort(i, ls);
}
int main()
{
read();
quickSort(1, n);
solve();
g << sum;
return 0;
}