Pagini recente » Cod sursa (job #1481840) | Cod sursa (job #1996725) | Cod sursa (job #21080) | Cod sursa (job #1272221) | Cod sursa (job #439747)
Cod sursa(job #439747)
#include <cstdio>
#include <algorithm>
using namespace std;
#define NMAX 100024
struct gutuie {
long t, g;
bool compg(gutuie x) const {
if (g < x.g)
return true;
return false;
}
bool operator<(gutuie x) const {
return compg(x);
}
};
long n, gmax;
gutuie a[NMAX];
void cit() {
long h, u;
long i, nn;
freopen("gutui.in", "rt", stdin);
scanf("%ld %ld %ld", &n, &h, &u);
nn = 0;
for (i = 0; i < n; i++) {
scanf("%ld %ld", &a[nn].t, &a[nn].g);
if (a[nn].t <= h) {
a[nn].t = (h - a[nn].t) / u;
nn++;
}
}
fclose(stdin);
}
bool compt(gutuie x, gutuie y) {
if (x.t == y.t) {
if (x.g > y.g)
return true;
return false;
}
if (x.t > y.t)
return true;
return false;
}
void rez() {
long lt, ng, i, hsize;
gutuie b[NMAX];
sort(a, a + n, compt);
/*for (i = 0; i < n; i++)
printf("%ld/%ld ", a[i].t, a[i].g);
printf("\n");*/
ng = 1;
lt = a[0].t;
hsize = 0;
gmax = 0;
for (i = 0; i < n; i++) {
if (lt != a[i].t) {
ng += lt - a[i].t;
if (i == n - 1)
ng += a[i].t;
lt = a[i].t;
}
b[hsize++] = a[i];
push_heap(b, b + hsize);
for (; ng > 0 && hsize > 0; ng--, hsize--) {
pop_heap(b, b + hsize);
gmax += b[hsize - 1].g;
}
/*for (int j = 0; j < hsize; j++)
printf("%ld/%ld ", b[j].g, b[j].t);
printf("\n");*/
}
}
void afis() {
freopen("gutui.out", "wt", stdout);
printf("%ld\n", gmax);
fclose(stdout);
}
int main() {
cit();
rez();
afis();
return 0;
}