Pagini recente » Cod sursa (job #685486) | Cod sursa (job #928708) | Cod sursa (job #376841) | Cod sursa (job #2096282) | Cod sursa (job #1848669)
#include <fstream>
#include <algorithm>
#define LMAX 100001
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
struct oaie{
int tura;
int lana;
};oaie o[LMAX];
int H[LMAX];
int n, L, x;
int lg;
int afisez;
void citire();
void sortare();
void rezolvare();
void afisare();
void inserare(int x);
void combinare(int i);
void creare();
int extragere_max();
bool criteriu(oaie a, oaie b);
int main()
{
citire();
sortare();
rezolvare();
afisare();
fin.close();
fout.close();
return 0;
}
void citire()
{
int i, d;
fin>>n>>x>>L;
for (i=1;i<=n;i++)
{
fin>>d>>o[i].lana;
o[i].tura=(x-d)/L+1;
}
n++;
lg=n;
}
void sortare()
{
sort (o+1, o+n+1, criteriu);
}
bool criteriu(oaie a, oaie b)
{
return a.tura>b.tura;
}
void rezolvare()
{
int i;
int tura=o[1].tura;
int ultim;
int dif;
for (i=1;1;i++)
if (o[i].tura==tura)
inserare(o[i].lana);
else
break;
ultim=tura;
n=i-1;
while (i<=lg)
{
tura=o[i].tura;
dif=ultim-tura;
while (dif>0)
{
afisez+=extragere_max();
dif--;
}
for (;i<=lg;i++)
if (o[i].tura==tura)
inserare(o[i].lana);
else break;
ultim=tura;
}
}
void combinare(int i)
{
//combin nodul H[i] cu heapurile cu radacinile H[2*i] si H[2*i+1]
int x=H[i], tata=i, fiu;
while (1)
{
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;
}
void creare()
{
int i;
for (i=n/2;i>0;i--)
combinare(i);
}
int extragere_max()
{
if (n==0)
return 0;
int maxim=H[1];
H[1]=H[n--];
combinare(1);
return maxim;
}
void inserare(int x)
{
int fiu=++n;
int tata=fiu/2;
while (tata && H[tata]<x)
{
H[fiu]=H[tata];
fiu=tata;
tata=fiu/2;
}
H[fiu]=x;
}
void afisare()
{
fout<<afisez<<'\n';
}