Cod sursa(job #441042)
Utilizator | Elena Diana Elena. | Data | 12 aprilie 2010 18:51:44 |
---|---|---|---|
Problema | Gutui | Scor | 60 |
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=1;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;
}