Cod sursa(job #440521)

Utilizator adriana.erbaruAdriana Erbaru adriana.erbaru Data 12 aprilie 2010 04:23:03
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.89 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
    {
        if (x.g == y.g)
        {   
            return 0;
        }
        else
        {
            return -1;
        }
    }

}

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 );
            
            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();
                
                sol.push_back(k);
                push_heap( sol.begin(), sol.end(), cmpG );
                
                // add(k); 
            }
    }                  
      
    fprintf(fout, "%li", gSol);
    
    fclose(fin);
    fclose(fout);
    return 0;
}