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