Pagini recente » Cod sursa (job #1579249) | Cod sursa (job #2860495) | Cod sursa (job #251158) | Cod sursa (job #3217058) | Cod sursa (job #2067259)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int n,x,l,i,t,h,dif;
long long s;
struct oaie
{
int dist,lana;
};
oaie o[100009],aux;
void down(int k, int n);
void up(int k, int n);
bool cmp(oaie a, oaie b){
if(a.dist<b.dist)return 1;
return 0;
}
int main()
{
fin>>n>>x>>l;
for(i=1;i<=n;i=i+1)
{
fin>>o[i].dist>>o[i].lana;
o[i].dist=x/l-(x-o[i].dist)/l;///am inlocuit distanta cu nivelul
}
sort(o+1, o+1+n, cmp);
o[n+1]={o[n].dist+1,0};///santinela
s=0;t=-1;h=0;///o[1..h] este heap-ul
for(i=1;i<=n+1;i++){
if(o[i].dist>t){
dif=o[i].dist-t;
while(h>0 && dif>0){
s=s+o[1].lana;
o[1]=o[h];
h--;
down(1,h);
dif--;
}
t=o[i].dist;
}
h++;o[h]=o[i];
up(h,h);
}
fout<<s;
fin.close();
fout.close();
return 0;
}
void down(int k, int n)
{
int t,f;
t=k;
f=2*k;
while(f<=n)
{
if(f<n)
{
if(o[f].lana<o[f+1].lana)
{
f=f+1;
}
}
if(o[t].lana<o[f].lana)
{
aux=o[t];
o[t]=o[f];
o[f]=aux;
t=f;
f=f*2;
}
else
{
f=n+1;
}
}
};
void up(int k, int n)
{
int t,f;
t=k/2;
f=k;
while(t && o[f].lana>o[t].lana)
{
aux=o[f];
o[f]=o[t];
o[t]=aux;
f=t;
t=t/2;
}
};