Cod sursa(job #460617)

Utilizator manu.georgetaManu Georgeta manu.georgeta Data 3 iunie 2010 13:43:37
Problema Gutui Scor 30
Compilator cpp Status done
Runda teme_upb Marime 2.02 kb
#include<stdio.h>
#include<malloc.h>
typedef struct {
	unsigned int inaltime;
	unsigned int greutate;
	} gutuie;
//interschimba doua elemente din vectorul de gutui
void swap(gutuie *a, gutuie *b) {
	gutuie aux;
	aux=*a;
	*a=*b;
	*b=aux;
}
int pivot(int i, int j) {
	return ((i+j)/2);
}
//sorteaza descrescator in functie de greutate in vectorul de gutui(sortare quicksort)
void qsort(gutuie *g, int m, int n) {	
	int key,i,j,k;
	if (m<n)
		{
			k=pivot(m,n);
			swap(&g[m],&g[k]);
			key=g[m].greutate;
			i=m+1;
			j=n;
			while (i<=j)
				{
				while ((i<=n) && ((int)g[i].greutate>=key))
					i++;
				while ((j>=m) && ((int)g[j].greutate<key))
					j--;
				if (i<j)
					swap(&g[i],&g[j]);
				}
			swap(&g[m],&g[j]);
			qsort(g,m,j-1);
			qsort(g,j+1,n);
		}
	}
int main() {
	unsigned int n,h,u,i,gt=0,cnt=0,j,localizare=0;
	FILE *in=fopen("gutui.in","r");
	FILE *out=fopen("gutui.out","w");
	
	fscanf(in,"%d",&n);

	gutuie *g=(gutuie*)malloc(n*sizeof(gutuie));
	unsigned int *ord=(unsigned int*)malloc(n*sizeof(unsigned int));
	unsigned int *maxim=(unsigned int*)malloc(n*sizeof(unsigned int));
    unsigned int *nrg=(unsigned int*)malloc(n*sizeof(unsigned int));
	//citire date	
	fscanf(in,"%u%u",&h,&u);
	for (i=0;i<n;i++)
		fscanf(in,"%u%u",&g[i].inaltime,&g[i].greutate);
	qsort(g,0,n-1);
	for (i=0;i<n;i++) {
	
			ord[i]=(h-g[i].inaltime)/u;
	}
	maxim[0]=nrg[0]=ord[0];
	gt=g[0].greutate;		
	for (i=1;i<n;i++) 
			{
				if (ord[i]>maxim[cnt]) {
					maxim[++cnt]=ord[i];
					nrg[cnt]=maxim[cnt]-maxim[cnt-1];
					gt+=g[i].greutate;
					nrg[cnt]--;
					}
				else {
					for (j=0;j<=cnt;j++) 
					{
						if (ord[i]<=maxim[j]) {localizare=j;break;}
					}
					for (;;) {
						if (nrg[localizare]>0) 
						{
							gt+=g[i].greutate;
							nrg[localizare]--;
							break;
						}
						else
							{
								if (localizare==0) break;
								localizare--;
							}
					}
								
					}
				}
	fprintf(out,"%u\n",gt,"\n");	
	fclose(out);
return 0;
}