Pagini recente » Cod sursa (job #549836) | Cod sursa (job #2968363) | Cod sursa (job #1248259) | Cod sursa (job #2384938) | Cod sursa (job #434825)
Cod sursa(job #434825)
#include <stdio.h>
#include <stdlib.h>
typedef struct gutui{
int h;
int g;
} gutui;
typedef struct node {
gutui fr;
struct node* next;
} node;
int partitie(gutui x[],int s,int d){
int piv=x[s].h;
int j=d+1,i=s-1;
gutui aux;
while(1){
do{j--;} while(x[j].h<piv);
do{i++;} while(x[i].h>piv);
if (i<j){
aux=x[i];
x[i]=x[j];
x[j]=aux;
}
else return j;
}
}
void quicksort(gutui x[],int s,int d){
if(s<d){
int p=partitie(x,s,d);
quicksort(x,s,p);
quicksort(x,p+1,d);
}
}
int main(){
FILE *f=fopen("gutui.in","r");
FILE *g=fopen("gutui.out","w");
int u,h,n,i;
gutui *fr;
node** zona;
fscanf(f,"%d%d%d",&n,&h,&u);
fr=(gutui*)malloc(n*sizeof(gutui));
for (i=0;i<n;i++)
fscanf(f,"%d%d",&fr[i].h,&fr[i].g);
//quicksort(fr,0,n-1);
node *p,*q;
int k=h/u+1,niv;
zona=(node**)calloc(k,sizeof(node*));
for (i=0;i<n;i++)
if (fr[i].h<=h){
p=(node*)malloc(sizeof(node));
p->fr=fr[i];
niv=fr[i].h/u;
if (zona[niv]==NULL){
p->next=NULL;
zona[niv]=p;
}
else
if (zona[niv]->fr.g<fr[i].g){
p->next=zona[niv];
zona[niv]=p;
}
else{
q=zona[niv];
while(q->next!=NULL&&q->next->fr.g>p->fr.g)
q=q->next;
p->next=q->next;
q->next=p;
}
}
/*
for (i=0;i<k;i++){
p=zona[i];
if (p==NULL) printf("gol");
while(p!=NULL){
printf("%d %d : ",p->fr.h,p->fr.g);
p=p->next;
}
printf("\n");
}
*/
int j=1,max,poz,s=0;
while (1){
max=-1;
poz=-1;
for (i=0;i<j;i++)
if(zona[i]!=NULL&&zona[i]->fr.g>max){
max=zona[i]->fr.g;
poz=i;
}
if (poz!=-1){
//printf("Am ales %d %d\n",zona[poz]->fr.h,zona[poz]->fr.g);
s+=zona[poz]->fr.g;
zona[poz]=zona[poz]->next;
}
j++;
if (j==k) break;
}
fprintf(g,"%d\n",s);
fclose(f);
fclose(g);
return 0;
}