Pagini recente » Cod sursa (job #1371203) | Cod sursa (job #590373) | Cod sursa (job #1600270) | Cod sursa (job #433789) | Cod sursa (job #440505)
Cod sursa(job #440505)
// nu e bun
#include<stdio.h>
#include<malloc.h>
typedef struct {
unsigned int inaltime;
unsigned int greutate;
} gutuie;
//interschimba 2 elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
gutuie aux;
aux=*a;
*a=*b;
*b=aux;
}
//auxiliar pentru functia de sortare quicksort
unsigned int choose_pivot(unsigned int i, unsigned int j) {
return ((i+j)/2);
}
//sorteaza descrescator in functie de greutate in vectorul de gutui
void quicksort(gutuie *g, unsigned int m, unsigned int n) {
unsigned int key,i,j,k;
if (m<n)
{
k=choose_pivot(m,n);
swap(&g[m],&g[k]);
key=g[m].greutate;
i=m+1;
j=n;
while (i<=j)
{
while ((i<=n)&&(g[i].greutate>=key))
i++;
while ((j>=m) &&(g[j].greutate<key))
j--;
if (i<j)
swap(&g[i],&g[j]);
}
swap(&g[m],&g[j]);
quicksort(g,m,j-1);
quicksort(g,j+1,n);
}
}
int main() {
//DECLARARI VARIABILE
unsigned int n,h,u,i,gt=0,cnt=-1,j,localizare;
FILE *in=fopen("gutui.in","r");
FILE *out=fopen("gutui.out","w");
fscanf(in,"%d",&n);
//ALOCARI DE MEMORIE
gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
unsigned int *ord=(unsigned int*)malloc(n*sizeof(unsigned int));
unsigned int *maxime=(unsigned int*)malloc(n*sizeof(unsigned int));
unsigned int *nrg=(unsigned int*)malloc(n*sizeof(unsigned int));
//CITIRE DIN FISIER SI COMPLETARE CAMPURI GUTUI
fscanf(in,"%d%d",&h,&u);
for (i=0;i<n;i++)
fscanf(in,"%d%d",&g[i].inaltime,&g[i].greutate);
/*
for (i=0;i<n;i++)
printf("%d %d\n",g[i].inaltime,g[i].greutate);
printf("\n");
*/
quicksort(g,0,n-1);
/*
for (i=0;i<n;i++)
printf("%d %d\n",g[i].inaltime,g[i].greutate);
printf("\n");
*/
//formez vectorul ord
for (i=0;i<n;i++) {
if (g[i].inaltime>h)
ord[i]=-1;
else
ord[i]=(h-g[i].inaltime)/u;
}
maxime[++cnt]=ord[0];
nrg[cnt]=ord[0];
gt=g[0].greutate;
for (i=0;i<n;i++)
if (ord[i]!=-1) {
if (ord[i]>maxime[cnt]) {
maxime[++cnt]=ord[i];
nrg[cnt]=maxime[cnt]-maxime[cnt-1];
gt+=g[i].greutate;
nrg[cnt]--;
}
else {
localizare=-1;
for (j=0;j<=cnt;j++)
if (ord[i]<=maxime[j]) {
localizare=j;
break;
}
while (localizare>=0) {
if (nrg[localizare]>0) {
gt+=g[i].greutate;
nrg[localizare]--;
break;
}
else
localizare--;
}
}
}
fprintf(out,"%d\n",gt);
return 0;
}