Pagini recente » Cod sursa (job #3187562) | Cod sursa (job #2900785) | Cod sursa (job #648251) | Cod sursa (job #2229606) | Cod sursa (job #441827)
Cod sursa(job #441827)
#include <stdlib.h>
#include <stdio.h>
int h[10000], g[10000], rm[10000], x[10000];
int i, j, H, U, k, aux;
long int n, sum=0;
static void quickSort (int g[], int lo, int hi)
{
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi;
int x=g[(lo+hi)/2];
// partition
do
{
while (g[i]>x) i++;
while (g[j]<x) j--;
if (i<=j)
{
aux = g[i]; g[i] = g[j]; g[j] = aux;
aux = h[i]; h[i] = h[j]; h[j] = aux;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quickSort(g, lo, j);
if (i<hi) quickSort(g, i, hi);
}
int main()
{
FILE* fin;
FILE* fout;
fin = fopen ("gutui.in", "r");
fout = fopen ("gutui.out", "w");
fscanf (fin, "%li %d %d", &n, &H, &U);
for ( i=0; i<n; i++)
fscanf ( fin, "%d %d", &h[i], &g[i] );
quickSort( g, 0, n-1);
for( i=0; i<n; i++)
printf("%d ", g[i]);
for( i=0; i<n; i++)
printf("%d ", h[i]);
printf("\n");
for( i=0; i<n; i++)
rm[i] = (H-h[i]) / U ;
int max=rm[0];
for( i=1; i<n; i++)
if(max < rm [i])
max = rm[i];
for( i=0; i<=max; i++)
x[i] = 0;
for( i=0; i<n; i++)
if( h[i] <= H )
{
if( x[ rm[i] ]==0 )
{
x[ rm[i] ] = g[i];
//printf("- %d -", x[(H-h[i]) / U]);
}
else if( x[ rm[i] ]!=0 )
for ( k= rm[i] -1 ; k>=0; k--)
if( x[k]==0 )
{
x[ k ] = g[i];
//printf("%d ", x[k]);
break;
}
}
/*
for( i=0; i<=max; i++)
printf("%d ", x[i]);
*/
for( i=0; i<=max; i++)
sum = sum + x[i];
fprintf(fout, "%li", sum);
fclose(fin);
fclose(fout);
return 0;
}