Cod sursa(job #439091)

Utilizator theonlyonealina sincu theonlyone Data 11 aprilie 2010 12:51:38
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 3.44 kb
#include<stdlib.h>
#include<stdio.h>
typedef struct{
		int height;
		int weight;
		}pom;
int compare(const void * a, const void * b){
	int * a1 = (int*)a;
	int * a2 = (int*)b;
	return *a1 - *a2;
}
void minweight(int a[],int b[],int n1,int n2,int limit){
    int i = 0,j = 0,l = 0;
    int c[n1 + n2];
    //for (j = 0; j<n2; j++)
    	//printf("%d ",b[j]);
    //printf("\n");
    //j = 0;
    while ((j<n1)&&(i<n2)){
      if ((a[j]>b[i]) && (a[j]!=0)) c[l++] = a[j++];
      else 
	c[l++] = b[i++];
    }
    
    for (;j<n1;j++)
      c[l++] = a[j];
    for (;i<n2;i++)
      c[l++] = b[i];
    l--;  
  //  printf("limit%d %d\n",limit,l);
    for (i = 0; i<n1-limit; i++)
    	a[i] = c[i];
    for(;i<n1; i++)
    	a[i] = 0;	
    	
    //for (i = 0; i<10; i++)
    	//printf("%d ",a[i]);
    //printf("\n");
      
}
int main(int argc, char * argv[]){
	int n,u,h,aux1,aux2,ind1,ind2,k,l;
	int i,j,x,ind,lung;
	unsigned int sum;
	FILE * fis = fopen("gutui.in","r");
	if (fis == NULL) printf("Couldn't open file\n");
	FILE * out = fopen("gutui.out","w");

	fscanf(fis,"%d",&n);
	fscanf(fis,"%d",&h);
	fscanf(fis,"%d",&u);
	
	pom * v = (pom*)malloc(n*sizeof(pom));
	int aux[n];
	int fin[n];
	
	for (i = 0; i<n; i++){
		fscanf(fis,"%d %d",&v[i].height,&v[i].weight);
		}
		
	int ord ;	
	do 	{
		ord  = 0;
		for (i = 0; i<n-1; i++){
			//if ((h - v[i].height)%u == 0) ind1 = (h - v[i].height)/u-1;
			//else
			 ind1 = (h - v[i].height)/u;
			//if ((h - v[i+1].height)%u == 0)ind2 = (h - v[i+1].height)/u-1;
			//else
			 ind2 =( h - v[i+1].height)/u;
			
			if (ind1 > ind2 ){
			
			   				 aux1 = v[i+1].height;
							 aux2 = v[i+1].weight;
							 v[i+1].height = v[i].height;
							 v[i+1].weight = v[i].weight;
							 v[i].height = aux1;
							 v[i].weight = aux2;
							 ord  = 1;
							 }
		 else if ((ind1 == ind2)&&(v[i].weight < v[i+1].weight)) {
		 	  				aux1 = v[i+1].height;
							 aux2 = v[i+1].weight;
							 v[i+1].height = v[i].height;
							 v[i+1].weight = v[i].weight;
							 v[i].height = aux1;
							 v[i].weight = aux2;
							 ord  = 1;
		 	  }
							 
		}			   
	}while (ord == 1);
	
	//qsort(v[i].height,n,sizeof(int),compare);
	
	//for (i = 0; i<n; i++)
	//	printf("%d %d\n",v[i].height,v[i].weight);
	
		
	for (i = 0; i<n; i++){
		fin[i] = 0;
	}
	
    	lung = 0;
    	aux1 = 0;
    	
    	//l = 0;
	for (i = 0; i<n; i++){
		//if ((h - v[i].height)%u == 0) ind1= (h - v[i].height)/u - 1;
		//else
		 ind1 = (h - v[i].height)/u;
		k =  ind1 + 1;
		ind2 =  ind1;
		j = i;
		
		aux1 = 0;
		l = 0;
		x = lung;
		while (ind2 == ind1){
		//	printf("%d h=%d g=%d \n",ind2,v[j].height + u*(lung+aux1),v[j].weight);
			if (k>0){
				if (v[j].height + u * (x+aux1) > h){
					//printf("aici %d lung=%d\n",fin[lung-l-1],lung);
					if ((v[j].weight > fin[lung-l-1]) && (fin[lung - l-1]!=0)){ l++;
				aux[aux1++] = v[j].weight;
				x--;}}
				else aux[aux1++] = v[j].weight;
			k--;	
			}
			
			j++;
			if (j == n) break;
		//	if ((h - v[j].height)%u == 0) ind2= (h - v[j].height)/u - 1;
				//else
				 ind2 = (h - v[j].height)/u;
			
		}
		
		lung = lung + aux1;
	//	printf("L:%d \n",lung);
		minweight(fin,aux,lung,aux1,l);
		lung = lung - l;
		i = j -1;	   				
	}
	
	sum = 0;
	x  = 0;
	//for (i = 0; i<n; i++){
	//	printf("%d ",fin[i]);
	//	x = x + fin[i];
	//	}
	//printf("%d",l);
	for (i = 0; i<lung; i++)
		sum = sum +fin[i];
//	printf("\n%d\n",sum);
	
	fprintf(out,"%d",sum);
	
	fclose(out);
	fclose(fis);
	return 0;
	
}