Cod sursa(job #440110)

Utilizator Cristea_AdrianCristea Adrian Cristea_Adrian Data 11 aprilie 2010 22:00:23
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.83 kb
#include <stdio.h>
#include <stdlib.h>
#include <map>

using namespace std;

typedef struct {
        int nivel;
        int masa;
        } Gutui;

int compare(const void *c, const void *d) {
     const Gutui *a = (const Gutui *)c;
     const Gutui *b = (const Gutui *)d;
     
     if(a->nivel!=b->nivel)
                         return (a->nivel - b->nivel);
     return(b->masa - a->masa);
}

int main() {
    int h_max, nr_gutui, d_h;
    int i, j, k, t, nr_puse=0;
    Gutui *gut;
    multimap <int, int > puse;
    multimap <int, int>::iterator iter;
    int strans=0;
    
    FILE *in, *out;

    in=fopen("gutui.in","r");
    out=fopen("gutui.out","w");
    
    fscanf(in,"%d ", &nr_gutui);
    fscanf(in,"%d ", &h_max);
    fscanf(in,"%d", &d_h);
        
    gut=(Gutui *)malloc(nr_gutui*sizeof(Gutui));
    
    for(i=0;i<nr_gutui;i++) {
         fscanf(in,"\n%d %d",&j, &gut[i].masa);
         gut[i].nivel=(h_max-j)/d_h+1;
         }
    
    qsort(gut, nr_gutui, sizeof(Gutui), compare);
    
    for(i=0;i<nr_gutui;i++) 
                            printf("%d %d \n", gut[i].nivel,gut[i].masa);
                            
    for(i=0;i<nr_gutui;i++) {
         if(gut[i].nivel-nr_puse>0) {
              puse.insert( pair<int, int> (gut[i].masa, 0)); 
              nr_puse++;
              printf("%d ",nr_puse);
         }
         else 
              if(gut[i].nivel-nr_puse==0)
                   if(gut[i].masa>(puse.begin())->first) {
                        puse.erase(puse.begin());
                        puse.insert( pair<int, int> ( gut[i].masa, 0));
                   }             
    }
    for(iter=puse.begin();iter!=puse.end();iter++) 
         strans+=iter->first;
    
    fprintf(out,"%d",strans);

    fclose(in);
    fclose(out);
           
    return 0;
}