Cod sursa(job #438945)
#include <stdio.h>
#include <stdlib.h>
struct fructa
{
long h, g, n;
};
long nSol = 0;
long sol[100000];
fructa f[100000];
long H, N, U;
int cmpN(const void * p, const void * q)
{
fructa x = *(fructa*)p;
fructa y = *(fructa*)q;
return (x.n-y.n);
}
void add(long k)
{
long i, j;
i = 0;
while ( ( f[sol[i]].g > f[k].g ) && ( i < nSol ) )
{
i++;
}
for (j=nSol; j>i; j--)
{
sol[j] = sol[j-1];
}
sol[i] = k;
}
int main()
{
long gSol = 0;
long i;
FILE *fin, *fout;
fin = fopen("gutui.in", "r");
fout = fopen("gutui.out", "w");
fscanf(fin, "%li%li%li", &N, &H, &U);
for (i=0; i<N; i++)
{
fscanf(fin, "%li%li", &f[i].h, &f[i].g);
f[i].n = (H-f[i].h) / U;
}
qsort(f, N, sizeof(fructa), cmpN);
long k;
for (k=0; k<N; k++)
{
// |S_(k-1)| = nSol
if (f[k].n >= nSol ) // n_k >= |S_(k-1)|
{
add(k);
nSol++;
gSol += f[k].g;
}
else // n_k < |S_(k-1)|
{
// in acest caz n_k + 1 = nSol
// cautam minimul in solutie
if ( f[sol[nSol-1]].g < f[k].g )
{
gSol = gSol + f[k].g - f[sol[nSol-1]].g;
add(k);
}
}
}
fprintf(fout, "%li", gSol);
fclose(fin);
fclose(fout);
return 0;
}