Pagini recente » Cod sursa (job #551140) | Cod sursa (job #1443934) | Cod sursa (job #2124089) | Cod sursa (job #2984846) | Cod sursa (job #435032)
Cod sursa(job #435032)
/*
Barca Cristian Mihai - 322CB
tema1 PA - prob2: Gutui
*/
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
typedef struct gutui {
int h, g, cules;
} TGUTUI;
int comp (const void *a, const void *b) {
TGUTUI x, y;
x = *(TGUTUI *)a;
y = *(TGUTUI *)b;
return (x.h - y.h);
}
int cautareBin(int i, int j, int elem, TGUTUI *A, int pond) {
int mij;
while (i < j) {
mij = (i + j)/2;
if ((elem + pond) > (A[mij].h + pond)) {
i = mij + 1;
}
else {
j = mij;
}
}
return j;
}
int main() {
TGUTUI A[NMAX];
int N, H, U, i, j;
int p1, p2, pond, max, sum, pozmax;
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", &A[i].h, &A[i].g);
A[i].cules = 0;
}
qsort(A + 1, N, sizeof(TGUTUI), comp);
i = N;
pond = max = sum = 0;
while (i > 1) {
while (A[i].h + pond > H || A[i].cules) i--;
p2 = i;
p1 = cautareBin(1, p2, A[p2].h - U, A, pond);
max = -A[p1].g;
for (j = p1; j <= p2; j++)
if (A[j].cules == 0 && max < A[j].g) {
max = A[j].g;
pozmax = j;
}
if (max > 0) {
A[pozmax].cules = 1;
sum += max;
}
pond = pond + U;
}
printf("%d\n", sum);
return 0;
}