Cod sursa(job #438938)

Utilizator adriana.erbaruAdriana Erbaru adriana.erbaru Data 11 aprilie 2010 04:59:00
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>

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

long nSol = 0;
long gSol = 0;
long sol[100000];

fructa f[100000];
long H, N, U;

int cmpN(const void * p, const void * q)  
{
    fructa x = *(fructa*)p;
    fructa y = *(fructa*)q;
    return (x.n-y.n);
}

void add(long k)
{
    long i;
    i=nSol-2;
    while (f[sol[i]].g < f[k].g )
    {
        i--;
    }
    for (long j=0; j<=i; j++)
    {
        sol[j] = sol[j+1];
    }
    sol[i+1] = k;
}   
    

int main()
{

    long i;
    
    FILE *fin, *fout;
    fin = fopen("gutui.in", "r");
    fout = fopen("gutui.out", "w");
    
    

    
    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);
    
    long k;
    
    
    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
            if ( f[sol[nSol-1]].g < f[k].g )
            {
                gSol = gSol + f[k].g - f[sol[nSol-1]].g;
                add(k); 
            }
        }
    }                  
      
    fprintf(fout, "%li", gSol);
    
    fclose(fin);
    fclose(fout);

    return 0;
}