Cod sursa(job #441328)

Utilizator corina_stemateStemate Corina Stefania corina_stemate Data 12 aprilie 2010 21:14:50
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 1.6 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct{
	unsigned int h,g,p;
}gutuie;


int comp(const void *a,const void* b){
gutuie* x=(gutuie*)a;
gutuie* y=(gutuie*)b;
if ( x->p==y->p) return y->g-x->g ;
return x->p-y->p;
}

int main(){


FILE *f;
f=fopen("gutui.in","r");

unsigned int n,h,u;

fscanf(f,"%d %d %d",&n,&h,&u);

int i,j;
gutuie *x,aux;
x=(gutuie*)malloc(n*sizeof(gutuie));

for (i=0;i<n;i++){
	fscanf(f,"%d %d\n",&x[i].h,&x[i].g);
	if (x[i].h > h) x[i].p=-1;
		else x[i].p=(h-x[i].h)/u;
}
fclose(f);
/*
for (i=0;i<n;i++)
	for (j=i+1;j<n;j++)
		if (x[i].p > x[j].p) {
					aux.h=x[i].h;
					aux.g=x[i].g;
					aux.p=x[i].p;
					x[i].h=x[j].h;
					x[i].g=x[j].g;
					x[i].p=x[j].p;
					x[j].h=aux.h;
					x[j].g=aux.g;
					x[j].p=aux.p;
		}
		else if (x[i].p==x[j].p){
				if (x[i].g < x[j].g) {
					aux.h=x[i].h;
					aux.g=x[i].g;
					x[i].h=x[j].h;
					x[i].g=x[j].g;
					x[j].h=aux.h;
					x[j].g=aux.g;
		}
}
*/
qsort(x,n,sizeof(gutuie),comp);
gutuie *s;
s=(gutuie*)malloc(n*sizeof(gutuie));


int k=0;
i=0;
int min;
while (i<n){
	if (x[i].p<0) i++;
	else{
		if (x[i].p>=k) {
			s[k].p=x[i].p;
			s[k].g=x[i].g;
			s[k].h=x[i].h;
			i++;
			k++;
		}
		else{
			if (k==0) i++;
				else {
					min=0;
					for(j=1;j<k;j++)
						if (s[j].g<s[min].g) min=j;
					if (x[i].g>s[min].g) {
							s[min].g=x[i].g;
							s[min].h=x[i].h;
							s[min].p=x[i].p;
					}
					i++;
				}
		}
	}
}
	 
int kg=0;
for (i=0;i<k;i++)
	kg=kg+s[i].g;
//printf("%d\n",kg);
/*
for (i=0;i<k;i++)
	printf("%d %d \n",s[i].h,s[i].g);
*/
FILE *g;
g=fopen("gutui.out","w");
fprintf(g,"%d",kg);
fclose(g);

return 0;
}