Cod sursa(job #463215)

Utilizator simona.poilincaSimona Poilinca simona.poilinca Data 14 iunie 2010 19:27:08
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.38 kb
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

int n=0;

typedef struct{
	int a;
	int b;
}gut;

//comparatorul meu pentru functia qsort
// le compar functie de greutati			
int compare(const void *x, const void *y){
	return ((gut *)x)->b  - ((gut *)y)->b;
}



int main ()
{
	  int  i,u,h;
	FILE *f1, *f2;
	 
	  gut * gutui;
	f1=fopen("gutui.in","r");
	f2=fopen("gutui.out", "w");
	fscanf(f1,"%d",&n);
	fscanf(f1,"%d",&h);
	fscanf(f1,"%d",&u);
	gutui = ( gut *)malloc( n* sizeof(  gut));

	
	for(i = 0; i < n; i++ ){
		fscanf(f1,"%d",&(gutui[i].a));
		fscanf(f1,"%d", &(gutui[i].b));
		
	}
	
	int s=0; 
	// le sortez
	qsort( gutui, n, sizeof(gut),compare);

	int max=0;
	for(i = 0; i < n; i++ )
		if((h-gutui[i].a)/u >max ) max= (h-gutui[i].a)/u;
	
	// vectorul unde imi voi pune greutatile
	 int *tmp;
	 tmp = (int*)calloc((max+1), sizeof(int));

	for(i = n-1; i >= 0; i-- ){
		
		if(gutui[i].a<=h)
		{	// daca in vectorul tmp pozitia respectiva e libera pun greutatea 
			// altfel  vad daca mai sunt pozitii anterioare in care sa pot pune grutatea
			if(tmp[(h-gutui[i].a)/u]==0)
				tmp[(h-gutui[i].a)/u]=gutui[i].b; 
			else
			{
				int  poz =(h-gutui[i].a)/u -1;
			
				while(poz>=0 && tmp[poz]!=0)
				{
				poz--;
				}
				if(poz >= 0) tmp[poz] =gutui[i].b;
			}
		}
	}
	
	for(i=0;i<max+1;i++)
		s=s+tmp[i];
	
	
    fprintf(f2,"%d",s);
    fclose(f1);fclose(f2); 
    
    return 0;
     
}