Cod sursa(job #437225)

Utilizator theonlyonealina sincu theonlyone Data 9 aprilie 2010 15:07:14
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.61 kb
#include<stdlib.h>
#include<stdio.h>
typedef struct{
		int * height;
		int * weight;
		int max;
		int el;
		int flag;
		}pom;

void minweight(int s[], int x,int n,int sign){
    int i = 0,j,l;
    if (sign == 1) j = 1; 
    else j = 0;
    //int * c = (int*)malloc(n*sizeof(int));
    int c[n];
    
    while (j<n){
      if ((s[j]< x) && (s[j]!=0)) c[i] = s[j];
      else 
	
	break;
      
      j++;
      i++;
    }
    
    c[i] = x;
    
    i++;
    for (;j<n;j++){
      c[i] = s[j];
      i++;
    }
    for (l = 0; l<n; l++)
      s[l] = c[l];
    
}
int main(int argc, char * argv[]){
	int n,u,h,hi,gi;
	int i,j,x,ind,s = 0;
	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((h/u)*sizeof(pom));


	for (i = 0; i<n; i++){
	  v[i].max = 0;
	  v[i].el = 0;
	  v[i].flag = 0;
	  v[i].height = (int*) malloc(sizeof(int));
	  v[i].weight = (int*) malloc(sizeof(int));
	}
	
	ind  = 0;
	for (i = 0; i<n; i++){
		fscanf(fis,"%d %d",&hi,&gi);
		
		if ((h - hi) % u == 0) ind = (h - hi)/u - 1;
		else ind =  (h - hi)/u;
		  v[ind].flag = 1;
	
		if (v[ind].max <= gi){
		  
		  v[ind].max  = gi;
		  if (ind + 1 > v[ind].el){
		    v[i].weight = (int*)realloc(v[i].weight,(v[ind].el+1)*sizeof(int));
		    v[i].height = (int*)realloc(v[i].height,(v[ind].el+1)*sizeof(int));
		    for (j = v[ind].el; j>0; j--){
		      v[ind].weight[j] = v[ind].weight[j-1];
		      v[ind].height[j] = v[ind].height[j-1];
		    }
		    v[ind].el++;
		  }else{
		    
		   if (ind + 1 == v[ind].el){
		    
		     for (j = v[ind].el-1; j>0; j--){
		       v[ind].weight[j] = v[ind].weight[j-1]; 
		       v[ind].height[j] = v[ind].height[j-1]; 
		     }
		   }
		  }
		v[ind].weight[0] = gi;
		v[ind].height[0] = hi;
		}
	}
	/*
	
	printf("\n");
	for (i = 0; i<h/u; i++){
	  if (v[i].flag == 1) {
	    printf("pom:%d %d",i,v[i].flag);
	    for (j = 0; j<v[i].el; j++)
	      printf("%d %d,",v[i].weight[j],v[i].height[j]);
	  }
	  printf("\n");
	}
	*/
	x = 0; 
	sum = (int*)calloc(n,sizeof(int));
	int a1;
	
	for (i = 0; i<h/u ; i++){
	 
	 if (v[i].flag == 1){
	   
	    
	   for (j = 0; j<v[i].el; j++){
	    
	    
	   if (v[i].height[j] + u*(x+1) <= h+u){
	     s = s + v[i].weight[j];
	     x++;
	     minweight(sum,v[i].weight[j],n,0);
	    }
	   else{
	      if (v[j].weight[j] > sum[0]){
	      s = s - sum[0];
	      s = s + v[i].weight[j];
	      minweight(sum,v[i].weight[j],n,1);
	     }
	   }
	   }
	 }
	 
	}
	
	
	//printf("%d",s);

	fprintf(out,"%d",s);
	
	fclose(out);
	fclose(fis);
	
	return 0;
	
}