Cod sursa(job #439288)

Utilizator dorinpislaruPislaru Dorin dorinpislaru Data 11 aprilie 2010 15:03:06
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.16 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct{
	  int g;
	  int h;
	  int nv;
}fruct;


int fsort(const void* a,const void* b){
		fruct* fr1=(fruct*)a;
		fruct* fr2=(fruct*)b;
		if(fr1->g == fr2->g) return fr1->h - fr2->h;
		return fr2->g - fr1->g;
}

int main(){
	 
	 int n,H,u;
	 int i,j,max=0;
	 FILE *f=fopen("gutui.in","r");
	 fscanf(f ,"%d" ,&n);
	 fscanf(f ,"%d" ,&H);
	 fscanf(f ,"%d" ,&u);
	 
	 fruct a[n];
	 int nrnv=H/u;
	 int hmin=10000;
	 
	 int v[nrnv];
	 for(i=0;i<nrnv;++i) v[i]=0;

	 for(i=0;i<n;++i)
	 {
		    fscanf(f ,"%d" ,&a[i].h);
		    if(a[i].h < hmin) hmin=a[i].h;
	 			fscanf(f ,"%d" ,&a[i].g);
	 			a[i].nv=(H-a[i].h)/u;
   }
   fclose(f);

	 qsort(a,n,sizeof(fruct),fsort);
	 
	 i=0;
	 while(hmin <= H && i < n)
	 {
	 				j=a[i].nv;
	 				while(j >= 0)
	        {
					 				if(v[j] == 0) 
								  {
									 				v[j]=a[i].g;
					          			max+=a[i].g;
					          			hmin+=u;
													break;
									}
					 				j--;
		      }
		      ++i;
		}			 				 													
		
		FILE* fout=fopen("gutui.out","w");
		fprintf(fout ,"%d" ,max);
		fclose(fout);
	
	 	return 0;
}