Pagini recente » Cod sursa (job #1543071) | Cod sursa (job #2948931) | Cod sursa (job #1348812) | Cod sursa (job #2180470) | Cod sursa (job #632493)
Cod sursa(job #632493)
#include <stdio.h>
#define NMAX 100005
struct nod{
int greutate, inaltime;
}v[NMAX];
int heap[NMAX],T[NMAX];
int noduri=1,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]=noduri;
noduri--;
coboara(1);
}
int poz(int li, int ls){
int ii=1,jj=0,a;
nod aux;
while(li<ls){
if(T[li]<T[ls]){
aux=v[li];
v[li]=v[ls];
v[ls]=aux;
a=T[li];
T[li]=T[ls];
T[ls]=a;
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 main(){
FILE *fin=fopen("gutui.in","r");
FILE *fout=fopen("gutui.out","w");
int N=0;
fscanf(fin,"%d%d%d",&N,&H,&U);
int i,inaltime, greutate,ind=1;
int tmax=-1;
for(i=1;i<=N;i++){
fscanf(fin,"%d%d",&inaltime,&greutate);
if(inaltime<=H){
v[ind].greutate=greutate;
v[ind].inaltime=inaltime;
T[ind]=(H-inaltime)/U+1;
if(T[ind]>tmax)tmax=T[ind];
ind++;
}
}
N=ind-1;
//sortez v descrescator dupa timp
sortare(1,N);
int indice=1;//locul in vector
int j,suma=0;
for(i=tmax;i>=1;i--){
//adaug in heap tot ce face parte din seria i
while(indice<=N && T[indice]==i){
//bag nodul indice in heap
heap[noduri]=indice;
urca(noduri);
noduri++;
indice++;
}
//afisez si extrag varful, daca heapul nu e vid
if(noduri>1){
suma+=v[heap[1]].greutate;
elimina();
}
}
fprintf(fout,"%d\n",suma);
return 0;
}