Cod sursa(job #441544)

Utilizator oana.fercheoana maria oana.ferche Data 12 aprilie 2010 23:05:46
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.8 kb
#include<stdio.h>
#include<stdlib.h>

#define MAX 100000

typedef struct t{
        long int alt;
        long int kg;
        } gutuie;




gutuie gutui[MAX];
int N;

long int U, H;

int tot[MAX];  //gutui culese
int nrc;     //nr gutui culese


int comparator (void *el1, void *el2){
    return ((gutuie*)el2)->alt - ((gutuie*)el1)->alt;
}


int minim(){
         int i;
         int min=0;
         for(i=1;i<nrc;i++){
                if(gutui[tot[i]].kg<gutui[tot[min]].kg)
                min=i;
                }
         return min;
         }
                                            


int main(){
   
   FILE *f;

f=fopen("gutui.in","r");
fscanf(f,"%d",&N);
fscanf(f,"%d",&H);
fscanf(f,"%d",&U);

int i,j;
long int aux;

for(i=0;i<N;i++){
                fscanf(f,"%d",&gutui[i].alt);
                fscanf(f,"%d",&gutui[i].kg);
                              
                } 
    
 
                
qsort(gutui, N, sizeof(gutuie),comparator);


long int hmax=H;
nrc=0;
for(i=0;i<N;i++){
                 if(gutui[i].alt<=hmax){
                                 tot[nrc++]=i;
                                 hmax-=U;
                                 }
                                 else
                                 {
                                     j=minim();  //elementul j din tot[] are greutatea minima
                                     if(gutui[i].kg>gutui[j].kg)
                                                    tot[j]=i;
                                 }
                 }
 long int total=0;
 
 for(i=0;i<nrc;i++){
                    total += gutui[tot[i]].kg;
                    }
                    
  
 FILE* g;
  g=fopen("gutui.out","w");
  fprintf(g,"%d",total);
  fclose(f);
  fclose(g);
 return 0;
}