Cod sursa(job #442417)

Utilizator hodoo_manrazvan ionita hodoo_man Data 14 aprilie 2010 14:51:39
Problema Gutui Scor 100
Compilator c Status done
Runda teme_upb Marime 1.9 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct g
{
    unsigned int inainte;
    unsigned int greu;
}gutui;
int compare (const void *x, const void *y)
{
    return -((*(gutui*)x).greu - (*(gutui*)y).greu);
}

int main()
{
    FILE *f, *g;
    f = fopen ("gutui.in", "r");
    g = fopen ("gutui.out", "w");
    
    unsigned int n, h, u, i, max=0, total=0, final[100000];
    //gutui gt[100000];
    fscanf (f, "%u", &n);
    fscanf (f, "%u", &h);
    fscanf (f, "%u", &u);
    gutui gt[n];
    for (i=0; i<n; i++)
    {
        fscanf (f, "%u", &gt[i].inainte);
        fscanf (f, "%u", &gt[i].greu);
        gt[i].inainte = (h - gt[i].inainte) / u; //cate gutui putem culege inaintea ei
        if (gt[i].inainte > max)
            max = gt[i].inainte;
    }    

    fclose (f); 
    qsort(gt, n, sizeof(gutui), compare);
    //unsigned int final[max+1];
    unsigned int index;
    int ok=1;
    /*for (i=0; i<=max; i++)
        //final[i] = 0;
        printf ("%u ", final[i]);
    printf ("\n"); */
    for (i=0; i<n; i++)
    {
        //printf("%u\n",i);
        //printf ("greutate: %u\n", gt[i].greu);
        //printf ("inainte: %u\n", gt[i].inainte);
        index = gt[i].inainte;
        ok = 1;
        //printf ("%u\n", gt[i].inainte);
        while (ok)
            if (final[index] >= gt[i].greu)
                if (index == 0)
                    ok = 0;
                else
                    index--;
            else
            {
                final[index] = gt[i].greu;
                ok = 0;
                //printf ("am pus la indexu: %u\n", index);
            }   
    }
    //printf("\n\n");
    //printf ("aici\n");
    /*for (i=0; i<=max; i++)
        printf ("%u\n", final[i]);
    printf("%u\n", total); */
    for (i=0; i<=max; i++)
        total += final[i];
    fprintf (g, "%u", total);
    fclose (g);
    return 0;
}