Pagini recente » Cod sursa (job #1978375) | Cod sursa (job #1215594) | Cod sursa (job #1782397) | Cod sursa (job #2932638) | Cod sursa (job #438050)
Cod sursa(job #438050)
#include <stdio.h>
#define NMAX 100001
struct sheap {
int v, ind;
} h[NMAX+1];
struct gutuie {
int h, g, tmin;
} gutui[NMAX+1];
int l_heap;
int T, N, H, U;
void propaga(int vf, int nn) {
int baza;
gutuie val = gutui[vf];
for (baza = 2 * vf; baza <= nn; baza *= 2) {
if (baza < nn && gutui[baza].tmin < gutui[baza + 1].tmin) ++baza;
if (val.tmin < gutui[baza].tmin) {
gutui[vf] = gutui[baza];
vf = baza;
}
else break;
}
gutui[vf]=val;
}
void heap() {
int i;
for (i = N/2; i >= 1; i--) propaga(i, N);
}
void heapsort() {
int i;
gutuie aux;
heap();
for (i = N; i > 1; i--) {
aux = gutui[i];
gutui[i] = gutui[1];
gutui[1] = aux;
propaga(1, i - 1);
}
}
void insert_heap(int timp, int ap) {
sheap val;
int vf, baza;
l_heap++;
h[l_heap].ind = timp;
h[l_heap].v = ap;
for (vf = l_heap, val = h[l_heap], baza = l_heap/2; baza > 0; baza /= 2) {
if (val.v < h[baza].v) {
h[vf] = h[baza];
vf = baza;
}
else break;
}
h[vf] = val;
}
void pop_heap(int &timp) {
sheap val;
int vf, baza;
timp = h[1].ind;
h[1] = h[l_heap];
l_heap--;
for (vf = 1, val = h[1], baza = 2; baza <= l_heap; baza *= 2) {
if (baza < l_heap && h[baza].v > h[baza + 1].v) baza++;
if (val.v > h[baza].v) {
h[vf] = h[baza];
vf = baza;
}
else break;
}
h[vf]=val;
}
int main() {
int last, i, j, k, timp;
long long totG = 0;
freopen("gutui.in", "rt", stdin);
freopen("gutui.out", "wt", stdout);
scanf("%d %d %d", &N, &H, &U);
for (i = 1; i <= N; i++) {
scanf("%d %d", &gutui[i].h, &gutui[i].g);
if (H < gutui[i].h) gutui[i].tmin = 0;
else gutui[i].tmin = (H - gutui[i].h)/U + 1;
}
heapsort();
for (i = 1; i <= N && !gutui[i].tmin; i++);
last = 1;
for (; i <= N; i = j) {
for (j = i; j <= N && gutui[j].tmin == gutui[i].tmin; j++);
for (; last <= gutui[i].tmin; last++) insert_heap(last, 0);
for (k = i; k < j; k++)
if (h[1].v < gutui[k].g) {
pop_heap(timp);
insert_heap(timp, gutui[k].g);
}
}
for (i = 1; i <= l_heap; i++) totG += h[i].v;
printf("%lld\n", totG);
return 0;
}