Cod sursa(job #436820)

Utilizator yeaaamihai simion yeaaa Data 8 aprilie 2010 23:41:07
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 2.16 kb
#include <stdio.h>
#include <stdlib.h>

#define  NMAX      100000

typedef struct gutuie{
        int in; // inaltime
        int gr; // greutate
        int ales;
} gutuie;

int compare (const void * a, const void * b)
{
  return ( ((gutuie*)b)->in - ((gutuie*)a)->in );
}

int minim(int v[], int n){
    int i;
    int min = 0;
    for(i = 1; i < n; i++){
          if(v[i] < v[min])
                  min = i;
    }
    return min;
}

int alegere(gutuie g[NMAX], int n, int h, int u){
    int rid = 0;; // ridicare curenta
    int i;
    int val = 0;
    int adaugate[NMAX];
    int nad = 0;
    int min;
    int trebuieAflat = 0;

    i = 0;
    while(i < n){
            
         if(g[i].in <= h){ //sa nu fie initial prea sus
            
            if((g[i].in + rid) <= h){
                 val += g[i].gr;
                 adaugate[nad] = g[i].gr;
                 nad++;
                 rid += u;
                 trebuieAflat = 1;
            } else{
                 if(trebuieAflat){
                      min = minim(adaugate,nad);
                      trebuieAflat = 0;
                 }
                 if(g[i].gr > adaugate[min]){
                      val -= adaugate[min];
                      val += g[i].gr;
                      adaugate[min] = g[i].gr;
                      trebuieAflat = 1;
                 }
            }
         }
            i++;            
    }
    return val;
}





int main(){
    FILE* f;
    int n, h, u;
    gutuie g[NMAX];
    int i;
    int rez;
    
    // citire
    f = fopen("gutui.in","r");
    fscanf(f,"%d %d %d",&n,&h,&u);
    for(i = 0; i < n; i++){
          fscanf(f,"%d %d", &g[i].in, &g[i].gr);
          g[i].ales = 0;
    }
    fclose(f);
    
    // aflare valoare
    qsort (g, n, sizeof(gutuie), compare);
    rez = alegere(g,n,h,u);
    
    // debugging
    printf("%d %d %d\n",n,h,u);
    for(i = 0; i < n; i++)   
       printf("%d %d\n",g[i].in, g[i].gr);
    printf("solutia: %d",rez);
    
    // scriere
    f = fopen("gutui.out","w");
    fprintf(f,"%d",rez);
    fclose(f);
    
    // terminare
    return 0;
}