Pagini recente » Cod sursa (job #1710991) | Cod sursa (job #197921) | Cod sursa (job #1701331) | Cod sursa (job #736880) | Cod sursa (job #632604)
Cod sursa(job #632604)
#include <stdio.h>
#define NMAX 100005
#define MAXIM 10005
struct nod{
int greutate, inaltime;
}v[NMAX];
int heap[NMAX];
int noduri,H,U;
void urca(int loc){
int x;
int aux;
while((x=loc/2) && v[heap[loc]].greutate>v[heap[x]].greutate){
//interschimb nodul de pe locul loc cu tatal sau
aux=heap[loc];
heap[loc]=heap[x];
heap[x]=aux;
loc=x;
}
}
void coboara(int loc){
//cobor in fiul cel mai mic dintre cei doi
int aux, x, y = 0;
while (loc != y){
y = loc;
if ((x=y*2)<=noduri && v[heap[loc]].greutate<v[heap[x]].greutate) loc = x;
x++;
if (x<=noduri && v[heap[loc]].greutate<v[heap[x]].greutate) loc = x;
aux = heap[loc];
heap[loc] = heap[y];
heap[y] = aux;
}
}
void elimina(){
//elimin varful heapului
heap[1]=heap[noduri];
noduri--;
coboara(1);
}
int poz(int li, int ls){
int ii=1,jj=0,a;
nod aux;
while(li<ls){
if(v[li].inaltime<v[ls].inaltime){
aux=v[li];
v[li]=v[ls];
v[ls]=aux;
a=ii;
ii=-jj;
jj=-a;
}
li+=ii;
ls+=jj;
}
return li;
}
void sortare(int li, int ls){
if(li<ls){
int k;
k=poz(li,ls);
sortare(li,k-1);
sortare(k+1,ls);
}
}
int pozitie=MAXIM-1;
char buff[MAXIM];//citesc bucati de cate maxim 10005 caractere
void cit(int &nr){
nr=0;
while(buff[pozitie]<'0' || buff[pozitie]>'9')//cat timp nu e cifra, treci mai departe
if (++pozitie==MAXIM){
fread (buff,1,MAXIM,stdin);
pozitie=0;
}
while('0'<=buff[pozitie] && buff[pozitie]<='9'){//cat timp e cifra
nr=nr*10+buff[pozitie]-'0';
if (++pozitie==MAXIM){
fread (buff,1,MAXIM,stdin);
pozitie=0;
}
}
}
int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int N=0;
scanf("%d%d%d",&N,&H,&U);
int i,inaltime, greutate,ind=1;
for(i=1;i<=N;i++){
cit(inaltime);
cit(greutate);
if(inaltime<=H){
v[ind].greutate=greutate;
v[ind].inaltime=(H-inaltime)/U+1;
ind++;
}
}
N=ind-1;
//sortez v descrescator dupa timp
sortare(1,N);
int indice=1;//locul in vector
int j,suma=0;
for(i=v[1].inaltime;i>0;i--){
//adaug in heap tot ce face parte din seria i
while(v[indice].inaltime==i){//sigur nu ies din vector, se termina cu un 0
//bag nodul indice in heap
noduri++;
heap[noduri]=indice;
urca(noduri);
indice++;
}
//printf("urmatoarea serie\n");
//afisez si extrag varful, daca heapul nu e vid
if(noduri>=1){
suma+=v[heap[1]].greutate;
elimina();
}
}
printf("%d\n",suma);
return 0;
}