Cod sursa(job #442518)

Utilizator AndreiBogdanCiobanu Andrei-Bogdan AndreiBogdan Data 14 aprilie 2010 18:43:20
Problema Gutui Scor 20
Compilator c Status done
Runda teme_upb Marime 2.19 kb
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
//#include<conio.h>

typedef struct {int i; int g;} Gutui;
int n, h, u, i;

int compare (const void * b, const void * a)
{
    int r;
    if ((h-(*(Gutui*)b).i)/u!=(h-(*(Gutui*)a).i)/u)
        r=((Gutui*)a)->i - (*(Gutui*)b).i;
    else
        r=((Gutui*)a)->g - (*(Gutui*)b).g;
    if (r>0) return 1;
        else if (r<0) return -1;
    return 0;
}

int main(){
        
   
    Gutui *g;
    int *c, picks=1, j;
    
    FILE *f,*f2;
    f=fopen("gutui.in","rt");
    f2=fopen("gutui.out","wt");
    
    fscanf(f,"%i",&n);
    fscanf(f,"%i",&h);
    fscanf(f,"%i",&u);
    g = (Gutui*)malloc(n*sizeof(Gutui));
    if (n<h/u)
        c=(int*)malloc(n*sizeof(int));
    else
        c=(int*)malloc((h/u+1)*sizeof(int));
    
    
    for (i=0;i<n;i++){
        fscanf(f,"%i",&g[i].i);
        fscanf(f,"%i",&g[i].g);
    }
    
    qsort (g, n, sizeof(Gutui), compare);
 
    c[0]=g[0].g;
    for (i=1;i<n;i++)
        if ((h-g[i].i)/u>=picks){
            if (c[picks-1]<g[i].g){
                for (j=picks-1;j>=0;j--)
                    if (c[j]<g[i].g)
                        c[j+1]=c[j];
                    else
                        break;
                j++;
                c[j]=g[i].g;
                picks++;
            }
            else
                c[picks++]=g[i].g;
        }
        else if ((h-g[i].i)/u>=picks-1){
            if (c[picks-1]<g[i].g){
                for (j=picks-2;j>=0;j--)
                    if (c[j]<g[i].g)
                        c[j+1]=c[j];
                    else{
                        if (j!=picks-2)
                            j--;
                        break;
                    }
                j++;
                c[j]=g[i].g;
            }
        }  
    /*       
    for (i=0;i<n;i++)
        printf("%i ",g[i].i);
    printf("\n"); 
    for (i=0;i<n;i++)
        printf("%i ",g[i].g);
    printf("\n"); 
    for (i=0;i<picks;i++)
        printf("%i ",c[i]);  
    printf("\n%i ",picks);
    */
    j=0;                  
    for (i=0;i<picks;i++)
        j+=c[i];
    fprintf(f2,"%i",j);
    //getch();
    return 0;
}