Pagini recente » Cod sursa (job #2426981) | Cod sursa (job #3032086) | Cod sursa (job #1591659) | Cod sursa (job #1610891) | Cod sursa (job #2067826)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int n,x,L,i,t,h,dif, dist;
long long s;
struct oaie{
int nivel,lana;
};
oaie o[100009],aux;
void down(int n);
void up(int n);
bool cmp(oaie a, oaie b){
if(a.nivel<b.nivel)return 1;
if(a.nivel==b.nivel && a.lana<b.lana)return 1;
return 0;
}
int main(){
fin>>n>>x>>L;
for(i=1;i<=n;i=i+1){
fin>>dist>>o[i].lana;
o[i].nivel=x/L-(x-dist)/L;///am calculat nivelul pe baza dist, L si x
}
sort(o+1, o+1+n, cmp);///sortare dupa nivel
///o[n+1] este santinela
o[n+1].nivel=o[n].nivel+1;
o[n+1].lana=0;
s=0;t=-1;h=0;///o[1..h] este heap-ul si initial este vid
for(i=1;i<=n+1;i++){
if(o[i].nivel>t){///am trecut la un nivel nou
dif=o[i].nivel-t;///diferenta de niveluri
while(h>0 && dif>0){
s=s+o[1].lana;
o[1]=o[h]; h--; dif--;
down(h);
}
t=o[i].nivel;
}
h++;o[h]=o[i];
up(h);
}
fout<<s;
fin.close();
fout.close();
return 0;
}
void down(int n){
int t,f;
t=1; f=2*t;
while(f<=n){
if(f<n && 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=2*t;
}
else break;
}
}
void up(int n){
int t,f;
f=n; t=f/2;
while(t>0 && o[f].lana>o[t].lana){
aux=o[f]; o[f]=o[t]; o[t]=aux;
f=t; t=f/2;
}
}