Cod sursa(job #441104)

Utilizator neoStyle89abc abc neoStyle89 Data 12 aprilie 2010 19:21:17
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 1.74 kb
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct mar {
    long h;
    long g;
} mar;
 
int n,ha,u;
mar a[1000],v[1000];
 
void afis() {
     int i;
     for(i=0;i<n;i++)
                     printf("%ld ",v[i].g);
     printf("\n");
}
 
void afisare() {
    int i;
    printf("%d ",n);
    printf("%d ",ha);
    printf("%d\n",u);
    for(i=0;i<n;i++)
        printf("%ld %ld\n", v[i].h,v[i].g );
    printf("\n");
}
 
void citire() {
   int i;
 
    FILE *f=fopen("gutui.in","r");
    fscanf(f , "%d%d%d" , &n , &ha , &u);

    for(i=0;i<n;i++)
    {
        fscanf( f, "%ld%ld" , &a[i].h , &a[i].g );
        a[i].h=ha-a[i].h;
    }
    fclose(f);
}

int compare (const void *a , const void *b) {
    return ( (*(mar*)a).h -  (*(mar*)b).h );
}

long gutui() {
    int i,j;
    float k=0;
    long x=0;
     
    qsort(a,n,sizeof(mar),compare);
     
    for(i=0;i<n;i++)
    {
        if( k <= (float)a[i].h/u )
        {
                      v[(int)k++]=a[i];
                      x+=a[i].g;
        }
        else
        {
            for(j=k-1;j>=0;j--)
                            if( a[i].g>v[j].g  )
                            {               
                                             x-=v[j].g;
                                             v[j]=a[i];
                                             x+=a[i].g;
                                             break;
                            }
        }
    }
    return x;
}
 
int main() {
    long x;
    FILE *g;
    citire();
    g=fopen("gutui.out","w");     
    x=gutui();
    fprintf(g,"%ld",x);
    //printf("%ld\n",x);
    //afisare();
     
    fclose(g);
    //system("pause");
    return 0;
}