Cod sursa(job #429910)

Utilizator oana.vasiuVasiu Oana-Alexandra oana.vasiu Data 30 martie 2010 16:41:55
Problema Gutui Scor 30
Compilator c Status done
Runda teme_upb Marime 1.74 kb
#include<stdio.h>
#include<stdlib.h>
struct gutui{
long h;
long g;
long nr_pasi;
int marcat;
};
typedef int (*compfn)(const void*, const void*);

long n, H, U;

int comparatorpasi(struct gutui *a, struct gutui *b){
	return (b->nr_pasi - a->nr_pasi);
}
int comparatorg(struct gutui *a, struct gutui *b){
	return (b->g - a->g);
}
//sortare dupa numarul de pasi pana nu se mai ajunge la gutui


int main(){
FILE* f=fopen("gutui.in","r");
FILE* g=fopen("gutui.out", "w");
fscanf(f,"%li %li %li",&n,&H,&U);
printf("%li %li %li \n",n,H,U);
struct gutui v[n];
long i;
long max=0;

for (i = 0 ; i < n ; i++){
	fscanf(f,"%li %li", &v[i].h, &v[i].g);
	v[i].nr_pasi =(( H - v[i].h ) / U) + 1 ;
//	if (v[i].h > H) v[i].nr_pasi=0;
	if ((max<v[i].nr_pasi)&&(v[i].h <= H)) max=v[i].nr_pasi;
	v[i].marcat=0;
	}
	
		
//printf("%i\n", max);
//for (i = 0 ; i < n ; i++)
//	printf("%i %i\n", v[i].h, v[i].g);
qsort(v, n, sizeof(struct gutui), (compfn)comparatorg);

//for (i=0; i<n; i++)
  //      printf("%i %i %i\n", v[i].h, v[i].g, v[i].nr_pasi);

long pas_curent=max;
long suma=0;
int m,j;

long cate[max];
for (i = 0 ; i < max ; i++){
	cate[i]=i+1;
	}
	
i=0;
long marcati=0;
while ( (pas_curent > 0) && (i < n) && (marcati < max) ){
//	for (j=0; j<max; j++)
//		printf("%i ", cate[j]);
//	printf("\n");
//	printf("%i\n",v[i].nr_pasi);
//	printf("\n");
	if ( (cate[v[i].nr_pasi-1] > 0) && (v[i].h <= H) ){
//		printf("%i\n",v[i].g);
		v[i].marcat=1;
		cate[v[i].nr_pasi-1]--;
		marcati++;
		}
//	printf("\n");
	i++;
	}
//qsort(v,n,sizeof(struct gutui),(compfn)comparatorpasi);
//printf("\n");
for (i=0; i<n; i++){
	if (v[i].marcat==1) suma=suma+v[i].g;
//	printf("%i %i %i \n", v[i].g, v[i].nr_pasi, v[i].marcat);
	}
//printf("%i",suma);
fprintf(g,"%li",suma);
close(f); 
close(g);
return 0;
}