Pagini recente » Cod sursa (job #54880) | Cod sursa (job #404559) | Cod sursa (job #3158750) | Cod sursa (job #1259185) | Cod sursa (job #437593)
Cod sursa(job #437593)
#include<stdio.h>
#include<stdlib.h>
#define N 100000
typedef struct gutui
{
int inaltime;
int greutate;
int moment; //momentul la care poate fi culeasa
}gutuie;
int compare(const void *p1,const void *p2)
{
float aux1,aux2;
gutuie *g1,*g2;
g1=(gutuie*)p1;
g2=(gutuie*)p2;
/*aux2=(float)g2->greutate/g2->moment;
aux1=(float)g1->greutate/g1->moment;
if(aux2>aux1)
return 1;
else
if(aux2==aux1)
return g1->moment-g2->moment;
return -1;*/
return g2->greutate-g1->greutate;
}
int maxim(int a,int b)
{
if(a>b)
return a;
return b;
}
int main()
{
int i,n,h,u;
int max=0;
int nr=0,sum=0,aux;
int culege[N]; //vectorul in care avem 1 daca la momentul i a fost culeasa o gutuie si 0 daca momentul este liber
FILE *in,*out;
in=fopen("gutui.in","r");
out=fopen("gutui.out","w");
gutuie gut[N];
fscanf(in,"%d",&n);
fscanf(in,"%d",&h);
fscanf(in,"%d",&u);
for(i=0;i<n;i++){
fscanf(in,"%d",&gut[i].inaltime);
fscanf(in,"%d",&gut[i].greutate);
gut[i].moment=(h-gut[i].inaltime)/u;
}
qsort(gut,n,sizeof(gutuie),compare);
for(i=0;i<n;i++)
culege[i]=0;
for(i=0;i<n;i++){
if(culege[gut[i].moment]==0){
culege[gut[i].moment]=1;
max=max+gut[i].greutate;
}
else{
aux=gut[i].moment;
while(aux>=0 && culege[aux]==1)
aux--;
if(aux>=0){
max=max+gut[i].greutate;
culege[aux]=1;
}
}
}
/*for(i=0;i<n;i++)
if(nr<gut[i].moment){
max=max+gut[i].greutate;
nr++;
}*/
//printf("%d",max);
fprintf(out,"%d",max);
return 0;
}