Pagini recente » Cod sursa (job #1280816) | Cod sursa (job #1432616) | Cod sursa (job #1972728) | Cod sursa (job #21320) | Cod sursa (job #1052572)
#include <fstream>
#include <algorithm>
#define Nmax 100005
using namespace std;
int N,X,L,H[Nmax];
struct pereche
{
int timp,lana;
bool operator <(const pereche &A) const
{
return timp<A.timp;
}
};
pereche t[Nmax];
inline void Swap(int i, int j)
{
int aux;
aux=H[i]; H[i]=H[j]; H[j]=aux;
}
inline void UpHeap(int k)
{
int tata;
tata=k/2;
while(k>1 && H[k]>H[tata])
{
Swap(k,tata);
k=tata; tata=k/2;
}
}
inline void DownHeap(int k)
{
int fiu,gata;
fiu=2*k; gata=0;
while(k<=H[0]/2 && !gata)
{
if(fiu+1<=H[0] && H[fiu+1]>H[fiu])
++fiu;
if(H[k]>=H[fiu])
gata=1;
else
{
Swap(k,fiu);
k=fiu; fiu=2*k;
}
}
}
inline void Read()
{
int i,dist,lana,len,timp;
ifstream fin("lupu.in");
fin>>len>>X>>L;
for(i=1;i<=len;++i)
{
fin>>dist>>lana;
timp=(X-dist)/L+1;
++N;
t[N].timp=timp; t[N].lana=lana;
}
fin.close();
}
inline void Solve()
{
int i,timp;
long long sol=0;
sort(t+1,t+N+1);
i=N; timp=t[N].timp;
while(timp>0)
{
while(i>0 && t[i].timp==timp)
{
H[++H[0]]=t[i].lana;
UpHeap(H[0]);
--i;
}
if(H[0])
{
sol+=H[1];
H[1]=H[H[0]--];
DownHeap(1);
}
--timp;
}
ofstream fout("lupu.out");
fout<<sol<<"\n";
fout.close();
}
int main()
{
Read();
Solve();
return 0;
}