Cod sursa(job #439616)

Utilizator petreanuandiPetreanu Adelin Andrei petreanuandi Data 11 aprilie 2010 17:33:52
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.68 kb
#include<stdio.h>
#include<stdlib.h>
#define N 100000
FILE *fin, *fout;
long long int n,h,u;
long long int aleg[N];

typedef struct gutuie{
	long long int nv;
	long long int g;
	} Gutuie;

Gutuie *pom;
int comp(const void * a, const void * b) {

	if ((*(Gutuie*) b).nv - (*(Gutuie*) a).nv < 0)
		return -1;
	else if ((*(Gutuie*) b).nv - (*(Gutuie*) a).nv == 0)
		return 0;
	else
		return 1;
}


int main(void) {
	fin = fopen("gutui.in", "r");
	fout = fopen("gutui.out", "w");
	long long int i,j;
	fscanf(fin, "%lld %lld %lld", &n, &h, &u);
	printf("%lld %lld %lld\n \n",n,h,u);
	long long int niv=(int) (h / u) + 1;
	long long int inaltimegutuie;
	pom=(Gutuie *) calloc (n,sizeof(struct gutuie));
	for (i = 0; i < n; i++) {
		fscanf(fin, "%lld %lld", &inaltimegutuie, &(pom[i].g));
		pom[i].nv=(h-inaltimegutuie)/u + 1;
		printf("%lld %lld %lld \n",inaltimegutuie, pom[i].nv, pom[i].g);
	}
	printf("\n \n");
	qsort(pom,n,sizeof(struct gutuie),comp);
	long long int pas=0;
	long long int aleg[n],min,ales;
	//ales=(long long int *) calloc (n,sizeof(long long int));	
	long long int suma=0;
	for(i=0;i<n;i++)
		printf(" %lld %lld \n" ,pom[i].nv, pom[i].g);
	for(i=n-1;i>=0;i--)
	{
		if( pas < pom[i].nv )
		{
			pas ++;
			aleg[pas]=pom[i].g;
			printf("am ales %lld \n ",aleg[pas]);
		}
		else
			if ( pas == pom[i].nv )
			{
				min=aleg[pas];
				for(j=1;j<=pas;j++)
					if( min > aleg[j] ) { min=aleg[j];ales=j; }
				if(pom[i].g > aleg[ales]) {
								printf("am inlocuit %lld cu %lld \n \n",aleg[ales],pom[i].g);
								aleg[ales]=pom[i].g;
							}
			}
	}
	for(i=1;i<=pas;i++)
	{
		printf("%lld ",aleg[i]);
		suma=suma+aleg[i];
	}	
			
		
	fprintf(fout,"%lld\n",suma);		
	fclose(fin);
	fclose(fout);
	return 0;
}