Cod sursa(job #436125)

Utilizator ion.morozanMorozan Ion ion.morozan Data 8 aprilie 2010 03:17:36
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 2.21 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef struct furcte{
    uint32_t  inaltime;
    uint32_t  greutate;
}fructe;

uint32_t sort_by_inaltime( const void *a, const void *b ){
    fructe *ia = ( fructe * )a;
    fructe *ib = ( fructe * )b;
    return (uint32_t)( ib->inaltime - ia->inaltime );
	/*  returns negative if b > a
            and positive if a > b. */
}

uint32_t sort_cresc( const void *a, const void *b ){
   return ( *(uint32_t*)a - *(uint32_t*)b );
	/*  returns negative if b > a
            and positive if a > b. */
}

int main(){
    FILE * f = fopen( "gutui.in", "r" );
    FILE * g = fopen( "gutui.out", "w" );
    uint32_t N,H,U,i, masa = 0;
    fructe x[100001];
    uint32_t min[100000];

     if ( f == NULL )                                       /* eroare la deschiderea fisierului */
         perror ("Error opening file");
    else{
         fscanf(f, "%u%u%u", &N, &H, &U  );                 /* nr de gutui, inaltimea maxima, cu cat creste distanta */

         for ( i = 0; i < N; i++){                           /* citirea elementelor structurii => greutatea si inaltimea unde se afla o gutuie */
             fscanf(f, "%u%u", &x[i].inaltime, &x[i].greutate );   
             min[i] = x[i].greutate;
         }
         
         qsort(x, N, sizeof(fructe), sort_by_inaltime);     /* sortez descrescator dupa inaltime */
         qsort(min, N, sizeof(uint32_t), sort_cresc);
        /*for ( i = 0; i < N; i++)
            printf("%u %u\n", x[i].inaltime, x[i].greutate);*/

         i = 0;
         uint32_t v = 0,nr=0;
         uint32_t k = 0;
         uint32_t t[100001];
         while ( i < N ){
             if ( (x[i].inaltime + k*U) <= H ){
                 masa +=t[k] = x[i].greutate;
                 v = x[i].greutate;
                 k++;
             }else{
                 //qsort(t,k,sizeof(uint32_t),sort_cresc);
                 if( (x[i].inaltime + (k-1)*U) <= H && x[i].greutate >= v ){
                     //masa -=t[0];
                     masa -=min[nr];
                     nr++;
                     masa +=t[0] = x[i].greutate;
                 }
             }
             i++;
         }
         fprintf(g, "%u", masa);

    }

    fclose(f);
    fclose(g);
    return 0;
}