Pagini recente » Istoria paginii runda/rastaluire | Cod sursa (job #2537254) | Cod sursa (job #2480199) | Cod sursa (job #2405279) | Cod sursa (job #440976)
Cod sursa(job #440976)
#include <stdio.h>
typedef struct { int h, g; } gutuie;
int compare ( void *a, void *b)
{
gutuie *g1= (gutuie*)a;
gutuie *g2= (gutuie*)b;
if( (*g2).h== (*g1).h)
return (*g2).g-(*g1).g;
return (*g2).h-(*g1).h;
}
int cmpint ( void *a, void *b)
{
long i1= *((int*)a);
long i2= *((int*)b);
return i1-i2;
}
long findmin( long * a, long sf, long *poz )
{
long i, min=a[0];
for( i=1;i<sf;i++)
if(min > a[i])
{
*poz=i;
min=a[i];
}
return min;
}
int main()
{
long n, h, u,i, maxg=0,j, max ;
gutuie g[100001];
long ia[100001],restu[100001], sf=0, poz,min, ultim, sf2=0;
FILE *f = fopen( "gutui.in", "rt" );
FILE *out = fopen ( "gutui.out", "wt");
fscanf(f, "%li %li %li", &n, &h, &u);
for( i=0; i<n;i++ )
fscanf (f, "%li %li", &(g[i].h), &(g[i].g) );
qsort( g, n, sizeof(gutuie) , compare ) ;
i=0;
while ( i<n && h >0 )
{
if ( g[i].h > h ) i++;
else if( g[i].h < h-u )
{
maxg += g[i].g;
ia[sf++]=g[i].g;
i++;
ultim=i;
h=h-u;
}
else
{
j=i+1;
max=g[i].g;
while ( j<n )
{
if( g[j].h < h-u ) break;
if ( max < g[j].g ) max = g[j].g;
j++;
}
maxg += max;
ia[sf++]=max;
i++;
ultim=i;
h=h-u;
}
}
// qsort( ia, sf, sizeof(long), cmpint);
if( ultim<n)
for( j=ultim; j<n; j++ )
{
min=findmin( ia, sf, &poz);
if( min < g[j].g )
{
printf("%li ", poz);
maxg= maxg - ia[poz];
maxg+= g[j].g;
ia[poz]=g[j].g;
}
}
fprintf( out, "%li", maxg);
// getch();
return 0;
}