Pagini recente » Cod sursa (job #2696455) | Cod sursa (job #2688595) | Cod sursa (job #37867) | Cod sursa (job #2669577) | Cod sursa (job #437226)
Cod sursa(job #437226)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int g, r;
}Fr;
typedef struct {
int *v, n;
}Vector;
int cmp(const void *a, const void *b) {
if( ((Fr*)a)->r != ((Fr*)b)->r )
return ((Fr*)b)->r - ((Fr*)a)->r;
return ((Fr*)b)->g - ((Fr*)a)->g;
}
void coboara(Vector ** heap, int dimHeap, int n) {
int st = 2 * n;
int dr = st + 1;
int max = n;
if(st < dimHeap && heap[st]->v[0] > heap[n]->v[0])
max = st;
if(dr < dimHeap && heap[dr]->v[0] > heap[n]->v[0])
max = dr;
if(max != n) {
Vector *v = heap[n];
heap[n] = heap[max];
heap[max] = v;
coboara(heap, dimHeap, max);
}
}
void urca(Vector ** heap, int dimHeap, int i) {
if(i <= 0)
return;
int p = i / 2;
if(heap[i]->v[0] > heap[p]->v[0]) {
Vector *v = heap[p];
heap[p] = heap[i];
heap[i] = v;
urca(heap, dimHeap, p);
}
}
int main() {
freopen("gutui.in", "r", stdin);
freopen("gutui.out", "w", stdout);
int n, s, k, i, j;
scanf("%d%d%d", &n, &s, &k);
Fr *a = (Fr*)(malloc(n * sizeof(Fr)));
Vector *v;
for(i = 0; n--;) {
scanf("%d%d", &(a[i].r), &(a[i].g));
if(a[i].r > s)
continue;
a[i].r = (s - a[i].r) / k;
i++;
}
qsort(a, n = i, sizeof(Fr), cmp);
int *buff, *origBuff = buff = (int*)malloc(n * sizeof(int));
Vector ** heap = (Vector**)malloc(n * sizeof(Vector*));
int dimHeap = 0;
int vf = 0, max = 0;
for(i = 0, j = s / k; j >= 0; j--) {
buff += vf;
vf = 0;
while(i < n && a[i].r >= j)
buff[vf++] = a[i++].g;
if(vf > 0) {
v = (Vector*)malloc(vf * sizeof(Vector));
v->n = vf;
v->v = buff;
heap[dimHeap++] = v;
urca(heap, dimHeap, dimHeap - 1);
}
if(dimHeap > 0) {
max += heap[0]->v[0];
heap[0]->v++;
heap[0]->n--;
if(heap[0]->n <= 0) {
free(heap[0]);
heap[0] = heap[--dimHeap];
}
coboara(heap, dimHeap, 0);
}
}
printf("%d\n", max);
free(a);
free(origBuff);
free(heap);
fclose(stdout);
return 0;
}