Cod sursa(job #427574)

Utilizator DonPushmeMilitaru Adrian DonPushme Data 28 martie 2010 00:28:20
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2 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-1;           
    }
/*    fprintf(g,"nr intervale:%d\n",interv);
    for(i=0;i<n;i++){
              fprintf(g,"%d %d\n", v[i].inaltime,v[i].greutate);       
    }*/
//    fprintf(g,"\n");   

    qsort (v, n, sizeof(fruct), compare);
 /*   for(i=0;i<n;i++){
            fprintf(g,"%d %d\n", v[i].inaltime,v[i].greutate);                
    }
    */
    int ponderi[100000];
    int hits[100000];
    for(i=0;i<n;i++){
       ponderi[i]=i+1;
       hits[i]=0;                 
    }
    int s=0;
 //  printf("\n");
    for(i=0;i<n;i++){
        if(ponderi[v[i].inaltime]!=0){ 
                s+=v[i].greutate;
                hits[v[i].inaltime]++;
/*                printf("hits:");
                for(int ii=0;ii<n;ii++){
                        printf("%d ",hits[ii]);        
                }*/
                        
                if(hits[v[i].inaltime]>1){
                      for(j=0;j<n;j++) ponderi[j]--;              
                }else {
                for(j=0;j<n;j++)
                                if(v[j].inaltime>=v[i].inaltime)   ponderi[j]--;
                }
/*                printf(" ponderi:");
                for(int ii=0;ii<n;ii++){
                        printf("%d ",ponderi[ii]);        
                }
                printf("\n");*/
        }
    }
    fprintf(g,"%d",s);
    fclose(f);
    fclose(g);
}