Pagini recente » Rating Martinescu Rares (Rares1) | Cod sursa (job #2048488) | Cod sursa (job #2645914) | Monitorul de evaluare | Cod sursa (job #438780)
Cod sursa(job #438780)
#include <stdio.h>
#include <stdlib.h>
typedef struct gutuie {
int wgt;
int hgt;
} gutuie;
int comp( const void *e1, const void *e2 ) {
gutuie *a = (gutuie*)(e1);
gutuie *b = (gutuie*)(e2);
if ( (*a).wgt == (*b).wgt )
return (*b).hgt - (*a).hgt;
return (*a).wgt - (*b).wgt;
}
int main() {
gutuie v[100000];
int aran[100000];
FILE *f = fopen( "gutui.in" , "r" );
FILE *g = fopen( "gutui.out", "w" );
int N, H, U, i, Wmax, X, j, Xmax;
fscanf ( f, "%d %d %d", &N, &H, &U );
for ( i=0; i<N; i++ ) {
fscanf( f, "%d %d", &v[i].hgt, &v[i].wgt);
aran[i] = -1;
}
Xmax = 0;
Wmax = 0;
qsort( v, N, sizeof(gutuie), comp );
/*for ( i=0; i<N; i++) {
printf("%d %d\n", v[i].hgt, v[i].wgt);
}*/
for ( i=N-1; i>=0; i-- ) {
X = (H - v[i].hgt) / U;
j = X+1;
if ( X<0) continue;
if ( X+1>Xmax ) Xmax = X+1;
while ( j>0 && aran[j]!=-1 ) j--;
if ( j>0 ) aran[j] = i;
/*if ( v[i].hgt + dH <= H ) {
Wmax += v[i].wgt;
dH += U;
if ( H < dH )
break;
}*/
}
for ( i=1; i<=Xmax; i++ ) {
if ( aran[i] != -1 ) Wmax += v[ aran[i] ].wgt;
}
/*for ( i=1; i<=Xmax; i++) {
printf("%d %d\n", v[ aran[i] ].hgt, v[ aran[i] ].wgt);
}*/
fprintf( g, "%d\n", Wmax );
fclose(f);
fclose(g);
return 0;
}