Pagini recente » Cod sursa (job #605352) | Cod sursa (job #1627300) | Cod sursa (job #632329) | Cod sursa (job #638398) | Cod sursa (job #433978)
Cod sursa(job #433978)
//Tigora Andrei 322CA
#include<stdio.h>
#include<stdlib.h>
typedef struct {
int w;
int h;
} gutuie;
typedef struct {
int max;
int crt;
int* w;
} heap;
int compare(gutuie a,gutuie b){
if(a.h<b.h)
return -1;
if(a.h>b.h)
return 1;
if(a.w>b.w)
return -1;
if(a.w<b.w)
return 1;
return 0;
}
void merge_sort(gutuie *vect,int size){
gutuie aux;
if(size==1)
return;
if(size==2){
if(compare(vect[0],vect[1])>0){
aux = vect[0];
vect[0] = vect[1];
vect[1] = aux;
}
return;
}
int middle = size/2,i,j,crt;
gutuie *vect1 = malloc((middle)*sizeof(gutuie));
gutuie *vect2 = malloc((size-middle)*sizeof(gutuie));
for(i=0;i<middle;i++)
vect1[i] = vect[i];
for(i=middle;i<size;i++)
vect2[i-middle] = vect[i];
merge_sort(vect1,middle);
merge_sort(vect2,size-middle);
i = 0, j = 0, crt = 0;
while(i<middle && j<size-middle)
if(compare(vect1[i],vect2[j])<=0)
vect[crt++] = vect1[i++];
else
vect[crt++] = vect2[j++];
while(i<middle)
vect[crt++] = vect1[i++];
while(j<size-middle)
vect[crt++] = vect2[j++];
free(vect1);free(vect2);
}
void remove_first(heap *choice){
choice->crt--;
choice->w[0] = choice->w[choice->crt];
int poz = 0;
int aux;
while(1){
if(poz*2+2<choice->crt){ //are ambii fii
if(choice->w[poz*2+1]<choice->w[poz]){//primul fiu mai mic decat curentul
if(choice->w[poz*2+2]<choice->w[poz*2+1]){//al doilea mai mic decat primul
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+2];
choice->w[poz*2+2] = aux;
poz = poz*2+2;
}
else{//primul mai mic decat al doilea
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+1];
choice->w[poz*2+1] = aux;
poz = poz*2+1;
}
}
else{//tatal mai mare ca primul fiu
if(choice->w[poz*2+2]<choice->w[poz]){//al doilea fiu mai mic
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+2];
choice->w[poz*2+2] = aux;
poz = poz*2+2;
}
else//ambii fii mai mari
break;
}
}
else //doar un fiu
if(poz*2+2<choice->crt){
if(choice->w[poz*2+1]<choice->w[poz]){//fiul este mai mic
aux = choice->w[poz];
choice->w[poz] = choice->w[poz*2+1];
choice->w[poz*2+1] = aux;
poz = poz*2+1;
}
else //fiul este mai mare
break;
}
else //nu are fii
break;
}
}
void add(heap *choice,int val){
int poz = choice->crt;
int aux;
choice->crt++;
choice->w[poz] = val;
while(poz)
if(choice->w[poz]<choice->w[(poz-1)/2]){
aux = choice->w[poz];
choice->w[poz] = choice->w[(poz-1)/2];
choice->w[(poz-1)/2] = aux;
poz = (poz-1)/2;
}
else
break;
}
int main(){
int i,crt,n;
gutuie *vect;
int high_max,low;
long long suma = 0;
heap choice;
FILE *in,*out;
//FILE *test;
in = fopen("gutui.in","r");
out = fopen("gutui.out","w");
//test = fopen("test.out","w");
fscanf(in,"%d%d%d",&n,&high_max,&low);
vect = malloc(n*sizeof(gutuie));
crt = 0;
for(i=0;i<n;i++){
fscanf(in,"%d%d",&vect[crt].h,&vect[crt].w);
if(vect[crt].h<=high_max){ // gutuie accesibila
crt++;
}
}
n = crt;
//for(i=0;i<n;i++)
// fprintf(test,"%d %d\n",vect[i].h,vect[i].w);
if(crt==0){
fprintf(out,"%lld",suma);
return 0;
}
// Inaltimea este inlocuita cu nivelul corespunzator
for(i=0;i<n;i++)
vect[i].h = ((high_max - vect[i].h) / low) + 1;
// Sorteaza corespunzator
merge_sort(vect,n);
//for(i=0;i<n;i++)
// fprintf(test,"%d %d\n",vect[i].h,vect[i].w);
// Initializeaza minheapul
if(vect[n-1].h > n){
choice.w = malloc(n*sizeof(int));
choice.max = n;
}
else{
choice.w = malloc(vect[n-1].h*sizeof(int));
choice.max = vect[n-1].h;
}
choice.crt=0;
// Adauga in minheap
for(i=0;i<n;i++){
if(vect[i].h>choice.crt)//mai sunt gutui accesibile pe nivelul curent
add(&choice,vect[i].w);
else if(vect[i].w > choice.w[0]){//gutuia curenta reprezinta o alegerea mai buna decat cea mai slaba alegere anterioara
remove_first(&choice);
add(&choice,vect[i].w);
}
}
while(choice.crt){
suma+=choice.w[0];
remove_first(&choice);
}
fprintf(out,"%lld",suma);
fclose(in);fclose(out);//fclose(test);
// End
return 0;
}