Cod sursa(job #434987)
Utilizator |
alex copot |
Data |
6 aprilie 2010 19:45:40 |
Problema |
Gutui |
Scor |
30 |
Compilator |
c |
Status |
done |
Runda |
teme_upb |
Marime |
1.87 kb |
#include <stdio.h>
#include <stdlib.h>
typedef struct {
unsigned long h;
unsigned long g;
} gutuie;
gutuie vg[100000];
long N, H, U;
void citeste()
{
FILE *f = fopen("gutui.in", "rt");
long i;
if ( f == NULL )
return;
fscanf(f, "%d%d%d", &N, &H, &U);
for (i = 0; i < N; i++)
fscanf(f, "%d%d", &vg[i].h, &vg[i].g);
fclose(f);
}
int comp1(const void *s1, const void *s2)
{
return ((gutuie*)s2)->h - ((gutuie*)s1)->h;
//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}
int comp2(const void *s1, const void *s2)
{
//return ((gutuie*)s2)->h - ((gutuie*)s1)->h;
return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}
int comp3(const void *s1, const void *s2)
{
return ((gutuie*)s2)->g - ((gutuie*)s1)->g;
//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}
int comp4(const void *s1, const void *s2)
{
return ( H - ((gutuie*)s1)->h ) / U - ( H - ((gutuie*)s2)->h ) / U;
//return (float) ((gutuie*)s2)->g / ((gutuie*)s2)->h - (float) ((gutuie*)s1)->g / ((gutuie*)s1)->h;
}
int main(int argc, char **argv)
{
unsigned long maxg, sg, sol;
unsigned long i, ncmax, nci;
citeste();
sg = 0;
qsort(vg, N, sizeof(gutuie), comp3);
i = 0;
ncmax = 0; // cate gutui voi culege
while (i < N) {
if ( (H - vg[i].h) / U + 1 > ncmax )
ncmax = (H - vg[i].h) / U + 1;
i++;
}
sol = 0;
for ( nci = 1; nci <= ncmax; nci++ ) {
maxg = vg[i].g;
sg = 0;
i = 0;
//nci =1
while ( i < N && nci <= ncmax ) {
if ((H - vg[i].h) / U + 1 == nci && vg[i].g > maxg) {
maxg = vg[i].g;
} else {
sg = sg + maxg;
maxg = vg[i].g;
nci++;
}
i++;
}
sg = sg + maxg;
if ( sg > sol)
sol = sg;
}
printf("%d\n", sol);
FILE *f = fopen("gutui.out", "wt");
fprintf(f, "%d\n", sol);
fclose(f);
return 0;
}