Pagini recente » Cod sursa (job #3277526) | Cod sursa (job #3203422) | Cod sursa (job #1478540) | Cod sursa (job #3203126) | Cod sursa (job #429991)
Cod sursa(job #429991)
Utilizator |
alex copot |
Data |
30 martie 2010 17:45:45 |
Problema |
Gutui |
Scor |
0 |
Compilator |
c |
Status |
done |
Runda |
teme_upb |
Marime |
1.77 kb |
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int h;
int g;
} gutuie;
gutuie vg[100000];
int N, H, U;
void citeste()
{
FILE *f = fopen("gutui.in", "rt");
int 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 main(int argc, char **argv)
{
int maxi_curent;
int maxg, sg, sg2;
int i, su;
citeste();
sg = 0;
/*
qsort(vg, N, sizeof(gutuie), comp1);
i = 1;
maxg = vg[0].g;
sg = 0;
maxi_curent = 0;
su = U;
while ( i < N ) {
if ( vg[i].h + su <= H )
if ( vg[maxi_curent].h - vg[i].h < U) {
if ( vg[i].g > maxg )
maxg = vg[i].g;
} else {
sg = sg + maxg;
maxg = vg[i].g;
su += U;
}
i++;
}
sg = sg + maxg;
*/
qsort(vg, N, sizeof(gutuie), comp3);
i = 1;
maxg = vg[0].g;
sg2 = 0;
maxi_curent = 0;
su = U;
while ( i < N ) {
if ( vg[i].h + su <= H )
if ( vg[maxi_curent].h - vg[i].h < U) {
if ( vg[i].g > maxg )
maxg = vg[i].g;
} else {
sg2 = sg2 + maxg;
maxg = vg[i].g;
su += U;
}
i++;
}
sg2 = sg2 + maxg;
if ( sg2 > sg )
sg = sg2;
FILE *f = fopen("gutui.out", "wt");
fprintf(f, "%d\n", sg);
fclose(f);
return 0;
}