Cod sursa(job #440030)

Utilizator CreationDinescu Stefan Creation Data 11 aprilie 2010 21:33:01
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 2.21 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct{
	int inaltime;
	int greutate;
	int index;
}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 compare1 (const void *a, const void *b){
	gutui *item1 = (gutui*)a;
	gutui *item2 = (gutui*)b;
	
	return (item1->inaltime - item2->inaltime);
}

int main(){
	FILE *fin=fopen("gutui.in","r");
	FILE *fout=fopen("gutui.out","w");
	
	int n,h,u;
	int i,j,k;
	int total=0;
	
	fscanf(fin,"%d %d %d",&n,&h,&u);
	
	gutui *v=(gutui*)malloc(n*sizeof(gutui));
	gutui *aux=(gutui*)malloc(n*sizeof(gutui));
	int *nivel=(int*)malloc(n*sizeof(int));
	
	for (i=0;i<n;i++){
		fscanf(fin,"%d %d",&v[i].inaltime,&v[i].greutate);
		v[i].index=i;
		aux[i].inaltime=v[i].inaltime;
		aux[i].greutate=v[i].greutate;
		aux[i].index=i;
	}
	
	qsort(aux,n,sizeof(gutui),compare1);
	qsort(v,n,sizeof(gutui),compare);
	
	
	
	///impartirea pe nivele a gutuilor
	for (i=0;i<n;i++)
		if (v[i].inaltime<=h)
			nivel[v[i].index]=(h-v[i].inaltime)/u+1;
			
	/*for (i=0;i<n;i++)
		printf("dupa inaltime %d %d %d %d\n",aux[i].inaltime,aux[i].index,aux[i].greutate,nivel[aux[i].index]);
		
	printf("\n\n");
	
	for (i=0;i<n;i++)
		printf("dupa greutate %d %d %d %d\n",v[i].greutate,v[i].index,v[i].inaltime,nivel[v[i].index]);*/
			
	/*for	(i=0;i<n;i++)
		printf("%d %d\n",v[i].inaltime,v[i].index);*/
			
	/*for (i=0;i<n;i++)
		printf("%d %d\n",nivel[v[i].index],v[i].inaltime);*/
	
	///descoperirea solutiei (pentru explicatie se consulta readme)
	for (i=0;i<n;i++){
		if (nivel[v[i].index]>0 && v[i].inaltime<=h){
			//printf("greutate=%d index=%d\n",v[i].greutate,v[i].index);
			total+=v[i].greutate;
			j=-1;
			k=nivel[v[i].index];
			while(1){
				j++;
				if (nivel[aux[j].index] < k || j>=n)
					break;
				//printf("%d %d\n",j,aux[j].index);
				if (nivel[aux[j].index]>0)
					nivel[aux[j].index]--;
			}
			/*printf("\nnivele:\n");
			for (j=0;j<n;j++)
				printf("%d %d %d\n",aux[j].inaltime,aux[j].index,nivel[aux[j].index]);
			printf("end nivele\n");
			printf("\n\n");*/
		}
	}
	
	
	fprintf(fout,"%d",total);///solutia finala
	fclose(fin);
	fclose(fout);
	free(v);
	free(nivel);
	return 0;
}