Pagini recente » Cod sursa (job #2463952) | Cod sursa (job #962269) | Cod sursa (job #1982779) | Autentificare | Cod sursa (job #425728)
Cod sursa(job #425728)
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int h, g;
} gutuie;
int cmp(const void *a, const void *b)
{
gutuie x, y;
x = *(gutuie *) a;
y = *(gutuie *) b;
if (x.h == y.h) return y.g - x.g;
return x.h - y.h;
}
int max(int a, int b)
{
if (a > b) return a;
return b;
}
int main()
{
int n, h, u, i, j, nr[100000], s, k;
FILE *fin, *fout;
fin = fopen("gutui.in", "rt");
fout = fopen("gutui.out", "wt");
fscanf(fin, "%i %i %i", &n, &h, &u);
gutuie v[100000];
for (i = 0; i < n; i++)
{
fscanf(fin, "%i %i", &(v[i].h), &(v[i].g));
v[i].h = (h - v[i].h) / u + 1;
}
qsort(v, n, sizeof(gutuie), cmp);
i = 0;
j = 0;
s = 0;
while (i < n)
{
if (v[i].h == j)
{
s++;
i++;
}
else
{
nr[j] = s;
s = 0;
j++;
}
}
k = j;
nr[k] = s;
fprintf(fout, "\n");
int **m, **suma;
m = (int **) malloc((n + k) * sizeof(int));
for (i = 0; i <= k; i++) m[i] = (int *) malloc(nr[i] * sizeof(int));
suma = (int **) malloc((n + k) * sizeof(int));
for (i = 0; i <= k; i++) suma[i] = (int *) malloc(nr[i] * sizeof(int));
s = 0;
for (i = 0; i <=k; i++)
{
suma[i][0] = 0;
for (j=1; j <= nr[i]; j++) suma[i][j] = suma[i][j-1] + v[s++].g;
}
for (i = 0; i <= k; i++)
if (nr[i] > i) nr[i] = i;
for (i = 0; i <= nr[k]; i++) m[k][i] = suma[k][i];
for (i = k-1; i >= 0; i--)
{
m[i][0] = m[i+1][nr[i+1]];
for (j = 1; j <= nr[i]; j++)
if (i+1-j > nr[i+1]) m[i][j] = max(m[i][j-1], suma[i][j] + m[i+1][nr[i+1]]);
else m[i][j] = max(m[i][j-1], suma[i][j] + m[i+1][i+1-j]);
}
fprintf(fout, "%i", m[0][nr[0]]);
fclose(fin);
fclose(fout);
return 0;
}