Cod sursa(job #427557)

Utilizator DonPushmeMilitaru Adrian DonPushme Data 27 martie 2010 23:56:34
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.27 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct fruct{
        int greutate;
        int inaltime;        
}fruct;

int compare (const void * a, const void * b)
{
      return (  ((fruct*)b)->greutate - ((fruct*)a)->greutate );
}
    
int main(){
    FILE* f,*g;
    int j;
    f=fopen("gutui.in","rt");
    g=fopen("gutui.out","wt");
    int n,h,u;
    fscanf(f,"%d%d%d",&n,&h,&u);
    int interv=h/u;
    int height;
    fruct* v;
    v=(fruct*)malloc(100000*sizeof(fruct));
    
    int i;
    for(i=0;i<n;i++){
              fscanf(f,"%d%d\n",&height,&v[i].greutate);
              v[i].inaltime=interv-height/u;           
    } 

    qsort (v, n, sizeof(fruct), compare);

    
    int ponderi[100000];
    int hits[100000];
    for(i=0;i<n;i++){
       ponderi[i]=i+1;
       hits[i]=0;                 
    }
    int s=0;
    
    for(i=0;i<n;i++){
        if(ponderi[v[i].inaltime-1]!=0){ 
                s+=v[i].greutate;
                hits[v[i].inaltime-1]++;
                
                
                if(hits[v[i].inaltime-1]>1){
                      for(j=0;j<n;j++) ponderi[j]--;              
                }else ponderi[v[i].inaltime-1]--;
        }
    }
    fprintf(g,"%d",s);
    fclose(f);
    fclose(g);
}