Cod sursa(job #438932)

Utilizator adriana.erbaruAdriana Erbaru adriana.erbaru Data 11 aprilie 2010 04:28:41
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 1.74 kb
#include <stdio.h>
#include <stdlib.h>

struct fructa
{
    long i, h, g, n;
};

int cmpN(const void * p, const void * q)  // (a,a1) <? (b,b1)
{
    fructa x = *(fructa*)p;
    fructa y = *(fructa*)q;
    return (x.n-y.n);
}

int cmpG(const void * p, const void * q)  // (a,a1) <? (b,b1)
{
    fructa x = *(fructa*)p;
    fructa y = *(fructa*)q;
    return (x.g-y.g);
}

int main()
{
    fructa f[100000];
    long H, N, U;
    long i;
    
    FILE *fin, *fout;
    fin = fopen("gutui.in", "r");
    fout = fopen("gutui.out", "w");
    
    
    long nSol = 0;
    long gSol = 0;
    long sol[100000];
    
    fscanf(fin, "%li%li%li", &N, &H, &U);
       
    for (i=0; i<N; i++)
    {
        fscanf(fin, "%li%li", &f[i].h, &f[i].g);
        f[i].n = (H-f[i].h) / U;
    }
    
    qsort(f, N, sizeof(fructa), cmpN);
    
    int k;
    
    int minSol;
    
    for (k=0; k<N; k++)
    {
        // |S_(k-1)| = nSol
        if (f[k].n >= nSol ) // n_k >= |S_(k-1)|
        {
            sol[nSol] = k;
            nSol++;
            gSol += f[k].g;
        }
        else // n_k < |S_(k-1)|
        {
            // in acest caz n_k + 1 = nSol
            // cautam minimul in solutie
            minSol = 0;
            for (i=0; i<nSol; i++)
            {
                if ( f[sol[i]].g < f[sol[minSol]].g )
                {
                    minSol = i;
                }
            }
            if ( f[sol[minSol]].g < f[k].g )
            {
                gSol = gSol + f[k].g - f[sol[minSol]].g;
                sol[minSol]=k;
            }
        }
    }                  
      
    fprintf(fout, "%li", gSol);
    
    fclose(fin);
    fclose(fout);

    return 0;
}