Cod sursa(job #437124)

Utilizator yeaaamihai simion yeaaa Data 9 aprilie 2010 13:25:17
Problema Gutui Scor 70
Compilator c Status done
Runda teme_upb Marime 2.64 kb
#include <stdio.h>
#include <stdlib.h>
//#include <conio.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)->gr/((gutuie*)b)->in - ((gutuie*)a)->gr/((gutuie*)a)->in );
  return ( ((gutuie*)b)->in - ((gutuie*)a)->in );
}

int compare2 (const void * a, const void * b)
{
  return ( *(int*)b - *(int*)a );
}

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 minim2(int v[],int a, int b){
    int m;
    int ms,md;
    if(a>=b) return b;
    m = (a+b)/2;
    ms = minim2(v,a,m);
    md = minim2(v,m+1,b);
    if(v[ms]<v[md]) return ms;
    return md;
}

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 trebuieSortat;
    int min;
    
    // treaba serioasa
    i = 0;
    while(i < n){
            if((g[i].in + rid) <= h){
                 val += g[i].gr;
                 adaugate[nad] = g[i].gr;
                 nad++;
                 rid += u;
                 //trebuieSortat = 1;
            } else{
                 //if(trebuieSortat){
                 //     qsort (adaugate, nad, sizeof(int), compare2);
                 //     trebuieSortat = 0;
                 //}
                 //min = minim(adaugate,nad);
                 min = minim2(adaugate,0,nad-1);
                 if(g[i].gr > adaugate[min]){
                      val -= adaugate[min];
                      val += g[i].gr;
                      adaugate[min] = g[i].gr;
                      //trebuieSortat = 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
//    getch();
    return 0;
}