Pagini recente » Cod sursa (job #1741067) | Cod sursa (job #567408) | Cod sursa (job #2618107) | Cod sursa (job #2981965) | Cod sursa (job #1847675)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
struct oaie
{
int t, a;
};
int nr, x, l, H[100010], s, n;
oaie o[100010];
void citire();
bool crit(oaie a, oaie b);
void rezolvare();
void inserare(int x);
void combinare(int i);
int extrage_max();
int main()
{
citire();
rezolvare();
fout << s << '\n';
fout.close();
return 0;
}
void citire()
{
int i, lg;
fin >> nr >> x >> l;
for (i = 1; i <= nr; i++)
{
fin >> lg >> o[i].a;
if (x >= lg)
o[i].t = (x - lg) / l + 1;
}
sort(o + 1, o + nr + 1, crit);
}
bool crit(oaie a, oaie b)
{
return a.t >= b.t;
}
void rezolvare()
{
int i = 1, zi, j;
zi = o[1].t;
if (x > 0)
{
while (o[i].t == zi)
{
H[++n] = o[i].a;
i++;
}
zi = o[i].t;
for (j = n / 2; j > 0; j--)
combinare(j);
for (j = 1; j <= o[i - 1].t - zi && H[1]; j++)
s += extrage_max();
while (zi > 0)
{
while (o[i].t == zi)
{
inserare(o[i].a);
i++;
}
for (j = 1; j <= zi - o[i].t && H[1]; j++)
s += extrage_max();
zi = o[i].t;
}
}
}
void inserare(int x)
{
int fiu = ++n, tata = fiu / 2;
while (tata && H[tata] < x)
{
H[fiu] = H[tata];
fiu = tata;
tata = fiu / 2;
}
H[fiu] = x;
}
void combinare(int i)
{
int x = H[i], tata = i, fiu;
while (true)
{
fiu = 2 * tata;
if (fiu > n)
break;
if (fiu + 1 <= n && H[fiu + 1] > H[fiu])
fiu++;
if (H[fiu] <= x)
break;
H[tata] = H[fiu];
tata = fiu;
}
H[tata] = x;
}
int extrage_max()
{
int maxim = H[1];
H[1] = H[n--];
combinare(1);
return maxim;
}