Cod sursa(job #436785)

Utilizator yeaaamihai simion yeaaa Data 8 aprilie 2010 23:11:09
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.86 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;

    i = 0;
    while(i < n){
            if((g[i].in + rid) <= h){
                 val += g[i].gr;
                 adaugate[nad] = g[i].gr;
                 nad++;
                 rid += u;
            } else{
                 min = minim(adaugate,nad);
                 if(g[i].gr > adaugate[min]){
                      val -= adaugate[min];
                      val += g[i].gr;
                      adaugate[min] = g[i].gr;
                 }
            }
            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;
}