Pagini recente » Cod sursa (job #471631) | Cod sursa (job #982663) | Cod sursa (job #2781876) | Cod sursa (job #3282877) | Cod sursa (job #498700)
Cod sursa(job #498700)
#include <stdio.h>
#include <stdlib.h>
typedef struct {
long g, r;
}Fr;
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 merge(long *v, long m, long d, long n) {
if(d <= m)
return;
long *v2 = (long *)malloc(n * sizeof(long));
long i = 0, j = m + 1, k = 0;
while(k < n && i <= m && j <= d)
if(v[i] > v[j])
v2[k++] = v[i++];
else
v2[k++] = v[j++];
while(k < n && i <= m)
v2[k++] = v[i++];
while(k < n && j <= d)
v2[k++] = v[j++];
for(i = 0; i < k; i++)
v[i] = v2[i];
free(v2);
}
int main() {
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
long n, s, k, i, j;
scanf("%ld%ld%ld", &n, &s, &k);
Fr *v = (Fr*)(malloc(n * sizeof(Fr)));
long *buff, *origBuff = buff = (long *)malloc(n * sizeof(long));
for(i = 0; n--;) {
scanf("%ld%ld", &(v[i].r), &(v[i].g));
if(v[i].r > s)
continue;
v[i].r = (s - v[i].r) / k;
i++;
}
qsort(v, n = i, sizeof(Fr), cmp);
long m, vf = -1, max = 0;
for(i = 0, j = s / k; j >= 0; j--) {
m = vf;
while(i < n && v[i].r >= j)
buff[++vf] = v[i++].g;
merge(buff, m, vf, j + 1);
if(vf > j)
vf = j;
if(vf >= 0) {
max += buff[0];
--vf;
++buff;
}
}
printf("%ld\n", max);
free(v);
free(origBuff);
fclose(stdout);
return 0;
}