Cod sursa(job #440523)

Utilizator adriana.erbaruAdriana Erbaru adriana.erbaru Data 12 aprilie 2010 04:36:19
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.52 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector.h>

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

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

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

int cmpG(long p, long q) 
{
    fructa x = f[p];
    fructa y = f[q];
    if (x.g > y.g )
    {
        return 1;
    }
    else
    {
        return 0;
    }

}

int main()
{

    long gSol=0, i, k;
    vector<long> sol;
    vector<long>::iterator it;
    
    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);
    
    for(k=0;k<N;k++)
    {
        // |S_(k-1)| = nSol
        if(f[k].n >= nSol) // n_k >= |S_(k-1)|
        {
            sol.push_back(k);
            push_heap( sol.begin(), sol.end(), cmpG );
            
            /* for (i=0; i<sol.size(); i++)
            {
                fprintf(fout, "%li", f[sol[i]].g);
                fprintf(fout, " ");
            } 
            
            fprintf(fout,"\n"); */
                
            
            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.front()].g < f[k].g)
            {
                gSol = gSol + f[k].g - f[sol.front()].g;
                
                pop_heap( sol.begin(), sol.end(), cmpG );
                sol.pop_back();
                
                /* for (i=0; i<sol.size(); i++)
                {
                    fprintf(fout, "%li", f[sol[i]].g);
                    fprintf(fout, " ");
                }
            
                fprintf(fout,"\n"); */
                
                sol.push_back(k);
                push_heap( sol.begin(), sol.end(), cmpG );
                
                /* for (i=0; i<sol.size(); i++)
                {
                    fprintf(fout, "%li", f[sol[i]].g);
                    fprintf(fout, " ");
                } 
            
                fprintf(fout,"\n"); */
                
                // add(k); 
            }
    }                  
      
    fprintf(fout, "%li", gSol);
    
    fclose(fin);
    fclose(fout);
    return 0;
}