Cod sursa(job #440786)

Utilizator ulitamoscalenco iulia ulita Data 12 aprilie 2010 15:35:57
Problema Gutui Scor 70
Compilator c Status done
Runda teme_upb Marime 1.46 kb
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

  long int n=0;


			

void sortg(long int *a, long int *b){
	long int i,j;
	
		for(i=0;i<n;i++)
			for(j=n-1;j>i;j--)
				if(b[j]< b[j-1]) {
					long int t1,t2;
					t1=a[j]; a[j]=a[j-1]; a[j-1]=t1;
					t2=b[j]; b[j]=b[j-1]; b[j-1] =t2;
				}
				
	
}


int main ()
{
	long int  i,u,h;
	FILE *f1, *f2;
	long int *a,*b;
	f1=fopen("gutui.in","r");
	f2=fopen("gutui.out", "w");
	fscanf(f1,"%ld",&n);
	fscanf(f1,"%ld",&h);
	fscanf(f1,"%ld",&u);
	a = ( long int*)malloc( n* sizeof( long int));
	b = ( long int*)malloc( n* sizeof( long int));
	
	for(i=0;i<n;i++){
		a[i]=(long int)malloc(sizeof(long int)); //inaltimile
		b[i]=(long int)malloc(sizeof(long int)); //greutatile

		fscanf(f1,"%ld",&a[i]);
		fscanf(f1,"%ld", &b[i]);
		
	}
	
	long int s=0; 
	
	sortg(a,b);
	//for(i=0;i<n;i++)
		//printf("%ld -",a[i]);
	int max=0;
	for(i=0;i<n;i++)
		if((h-a[i])/u >max ) max= (h-a[i])/u;
	
	
	int k=0;
	for(i=0;i<n;i++)
		if(((h-a[i])/u)==max) k++;

	//max=k;
	//printf("min%d ", max);
	 int *tmp;
	 tmp= (int*)malloc((max+1)*sizeof(int));
	for(i=0;i<max+1;i++)
		tmp[i]=0;
		
	for(i=n-1;i>=0;i--){
		if(a[i]<=h){
		if(tmp[(h-a[i])/u]==0)
			tmp[(h-a[i])/u]=b[i]; /*printf("%ld ", a[i]);*/
		else
		{
			int  poz =(h-a[i])/u -1;
			while(poz>=0 && tmp[poz]!=0){
			 poz--;
			}
			
			 if(poz>=0) tmp[poz] =b[i];
		 }
	 }
		}
	
	for(i=0;i<max+1;i++)
		s=s+tmp[i];
	
	
    fprintf(f2,"%ld",s);
    fclose(f1);fclose(f2); 
    return 0;
     
}