Cod sursa(job #440521)
#include <stdio.h>
#include <stdlib.h>
#include <vector.h>
struct fructa
{
long h, g, n;
};
long nSol, H, N, U;
fructa f[100000];
int cmpN(const void * p, const void * q)
{
fructa x = *(fructa*)p;
fructa y = *(fructa*)q;
return (x.n - y.n);
}
int cmpG(long p, long q)
{
fructa x = f[p];
fructa y = f[q];
if (x.g < y.g )
{
return 1;
}
else
{
if (x.g == y.g)
{
return 0;
}
else
{
return -1;
}
}
}
int main()
{
long gSol=0, i, k;
vector<long> sol;
vector<long>::iterator it;
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);
for(k=0;k<N;k++)
{
// |S_(k-1)| = nSol
if(f[k].n >= nSol) // n_k >= |S_(k-1)|
{
sol.push_back(k);
push_heap( sol.begin(), sol.end(), cmpG );
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.front()].g < f[k].g)
{
gSol = gSol + f[k].g - f[sol.front()].g;
pop_heap( sol.begin(), sol.end(), cmpG );
sol.pop_back();
sol.push_back(k);
push_heap( sol.begin(), sol.end(), cmpG );
// add(k);
}
}
fprintf(fout, "%li", gSol);
fclose(fin);
fclose(fout);
return 0;
}