Pagini recente » Cod sursa (job #2801738) | Cod sursa (job #2180647) | Cod sursa (job #3128255) | Cod sursa (job #1777849) | Cod sursa (job #431926)
Cod sursa(job #431926)
#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);
zona=(node**)malloc(n*sizeof(node*));
node *p,*q;
int k=-1;
int r=-1;
for (i=0;i<n;i++){
p=(node*)malloc(sizeof(node));
p->fr=fr[i];
if ((h-fr[i].h)/u==r){
//p->next=zona[k];
//zona[k]=p;
if (zona[k]->fr.g<p->fr.g){
p->next=zona[k];
zona[k]=p;
}
else{
q=zona[k];
while(q->next!=NULL&&q->next->fr.g>p->fr.g)
q=q->next;
p->next=q->next;
q->next=p;
}
//printf("%d %d|",fr[i].h,fr[i].g);
}
else {
k++;
p->next=NULL;
zona[k]=p;
//printf("\n");
//printf("%d %d|",fr[i].h,fr[i].g);
r=(h-fr[i].h)/u;
}
}
k++;
/*
for (i=0;i<k;i++){
p=zona[i];
while(p!=NULL){
printf("%d %d : ",p->fr.h,p->fr.g);
p=p->next;
}
printf("\n");
}
*/
int j=1,max,poz,s=0,ok=0,hi=0;
while (1){
max=-1;
ok=0;
for (i=0;i<j;i++)
if(zona[i]!=NULL&&zona[i]->fr.g>max&&zona[i]->fr.h+hi<=h){
max=zona[i]->fr.g;
poz=i;
ok=1;
}
if(ok==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;
hi=hi+u;
}
else
j++;
if (j==k+1) break;
}
fprintf(g,"%d\n",s);
//for (i=0;i<n;i++)
// printf("%d %d\n",fr[i].h,fr[i].g);
fclose(f);
fclose(g);
return 0;
}