Cod sursa(job #441003)

Utilizator CreationDinescu Stefan Creation Data 12 aprilie 2010 18:38:02
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.75 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct{
	int inaltime;
	int greutate;
}gutui;

//functie comparare pentru qsort
int compare (const void *a, const void *b){
	gutui *item1 = (gutui*)a;
	gutui *item2 = (gutui*)b;
	
	return -(item1->greutate - item2->greutate);
}

int main(){
	FILE *fin=fopen("gutui.in","r");
	FILE *fout=fopen("gutui.out","w");
	
	int n,h,u;
	int i,j,maxim,min=0;
	int total=0;
	
	fscanf(fin,"%d %d %d",&n,&h,&u);
	
	gutui *v=(gutui*)malloc(n*sizeof(gutui));
	//int *nivel=(int*)malloc(n*sizeof(int));
	int *level=(int*)malloc((h/u+2)*sizeof(int));
	
	for (i=1;i<=h/u+1;i++)
		level[i]=i;
	
	
	for (i=0;i<n;i++){
		fscanf(fin,"%d %d",&v[i].inaltime,&v[i].greutate);
		if (i==0)
			min=v[i].inaltime;
		else if (min>v[i].inaltime)
			min=v[i].inaltime;
	}
		
	qsort(v,n,sizeof(gutui),compare);
	
	//impartirea pe nivele a gutuilor
	/*for (i=0;i<n;i++)
		if (v[i].inaltime<=h)
			nivel[i]=(h-v[i].inaltime)/u+1;*/
			
	maxim=(h-min)/u+1;

	
	//descoperirea solutiei (pentru explicatie se consulta readme)
	for (i=0;i<n;i++){
		if (level[(h-v[i].inaltime)/u+1]>0 && v[i].inaltime<=h){
			/*printf("level:  ");
			for (j=1;j<=maxim;j++)
				printf("%d ",level[j]);
					printf("\n");
			printf("greutate=%d inaltime = %d\n",v[i].greutate,(h-v[i].inaltime)/u+1);*/
			total+=v[i].greutate;
			min=level[(h-v[i].inaltime)/u+1];
			for (j=maxim;j>=1;j--)
				if (level[j]>=min && level[j]>0)
					level[j]--;
				else if (level[j]>0)
					break;
			/*for (j=1;j<=h/u+1;j++)
				if (level[j]>0 && level[j]>=level[(h-v[i].inaltime)/u+1])
					level[j]--;*/
			/*for (j=i+1;j<n;j++)
				if (nivel[j] >= nivel[i])
					nivel[j]--;*/
		}
	}
	
	
	fprintf(fout,"%d",total);//solutia finala
	fclose(fin);
	fclose(fout);
	free(v);
	//free(nivel);
	free(level);
	return 0;
}