Cod sursa(job #441010)

Utilizator Elena.Elena Diana Elena. Data 12 aprilie 2010 18:41:58
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.28 kb
/*BUCHIR Elena
     325CC*/

#include <stdio.h>
#include <stdlib.h>

typedef struct{
        long int h,g;
        int pas;
        }gutuie;

int minim(int a, int b){
    if(a<b) return a;
    else return b;
}
//functie care compara doua gutui dupa inaltime
int compara_gutuie(const void *a, const void *b)
{
	gutuie * g1 = (gutuie*) a;
	gutuie * g2 = (gutuie*) b;
	return g2 -> h - g1 -> h;
	return 0;
//return (g2->h - g1->h);
}

int main(){
    FILE* f=fopen("gutui.in","r");
    FILE* p=fopen("gutui.out","w"); 
    long int N, H, U;
    int tmin=1,min;
    int i,j; 
    fscanf(f,"%ld %ld %ld",&N,&H,&U); 
    //gutuie* x;
    //int* sol;
    //x=(gutuie*)malloc(N*sizeof(gutuie));
    //sol=(int*)malloc(N*sizeof(int));
    gutuie x[100000];
    int sol[100000];
    int max=x[0].g;
    sol[1]=x[0].g;
    for(i=0;i<N;i++){                                                                                                                                                                                                                                                  
                     fscanf(f,"%ld %ld",&x[i].h,&x[i].g);}
                      
    qsort(x,N,sizeof(gutuie),compara_gutuie); //sortez vectorul de gutui descrescator dupa inaltime
    /*for(i=0;i<N;i++){printf("%ld %ld",x[i].h,x[i].g);
                                 printf("\n");}*/
    for(i=0;i<N;i++){
                     x[i].pas=(H-x[i].h)/U;
                     min=minim(x[i].pas,tmin);
                     for(j=min+1;j>=1;j--)
                                          if((sol[j-1]+x[i].g)>sol[j]){
                                                                      sol[j]=sol[j-1]+x[i].g;
                                                                      if(sol[j]>max)
                                                                           max=sol[j];
                                                                      if(j==min+1)
                                                                           tmin++;
                                                                           }
                     }
                     
                  
    //fprintf(p,"%d",max);
    printf("%d",max);
    fclose(f);
    fclose(p);
    getchar();
    return 0;
}