Pagini recente » Cod sursa (job #2581198) | Istoria paginii utilizator/banescueduard123 | Cod sursa (job #440514) | Cod sursa (job #1282620) | Cod sursa (job #441561)
Cod sursa(job #441561)
#include <stdlib.h>
#include <stdio.h>
//#include <conio.h>
int h[10000], g[10000], rm[10000], x[10000];
int i, j, H, U, k;
long int n, sum=0;
int partition( int g[], int l, int r) {
int pivot, i, j, aux;
pivot = g[l];
i = l; j = r;
while( 1)
{
do ++i; while( g[i] <= pivot && i <= r );
do --j; while( g[j] > pivot );
if( i >= j ) break;
aux = g[i]; g[i] = g[j]; g[j] = aux;
aux = h[i]; h[i] = h[j]; h[j] = aux;
}
aux = g[l]; g[l] = g[j]; g[j] = aux;
aux = h[l]; h[l] = h[j]; h[j] = aux;
return j;
}
void quickSort( int g[], int l, int r)
{
int j;
if( l < r )
{
j = partition( g, l, r);
quickSort( g, l, j-1);
quickSort( g, j+1, r);
}
}
int main()
{
int aux;
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);
for(i=0; i<n/2; i++)
{
aux = g[i]; g[i]=g[n-i]; g[n-i]=aux;
aux = h[i]; h[i]=h[n-i]; h[n-i]=aux;
}
for(i=0; i<n; i++)
{
g[i]=g[i+1];
h[i]=h[i+1];
}
/*
for( i=0; i<n; i++)
printf("%d ", g[i]);
for( i=0; i<n; i++)
printf("%d ", h[i]);
*/
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[ (H-h[i]) / U ]==0 )
x[ (H-h[i]) / U ] = g[i];
}
else
for ( k=((H-h[i]) / U )-1; k>=0; k--)
if( x[k]==0 )
{
x[ k ] = g[i];
break;
}
for( i=0; i<=max; i++)
sum = sum + x[i];
fprintf(fout, "%d", sum);
fclose(fin);
fclose(fout);
//getch();
return 0;
}