Pagini recente » Cod sursa (job #646981) | Cod sursa (job #489291) | Cod sursa (job #885150) | Cod sursa (job #3040236) | Cod sursa (job #426325)
Cod sursa(job #426325)
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int h, g;
} gutuie;
int a[2][100000];
gutuie v[100000];
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;
FILE *fin, *fout;
fin = fopen("gutui.in", "rt");
fout = fopen("gutui.out", "wt");
fscanf(fin, "%i %i %i", &n, &h, &u);
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;
if(v[i].h < 0) v[i].h = 0;
}
qsort(v, n, sizeof(gutuie), cmp);
for (i = 0; i < n; i++)
for (j = 1; j <= v[i].h && j <= n; j++)
a[(i+1)%2][j] = max(a[i%2][j-1] + v[i].g, a[i%2][j]);
int max = 0;
for (i = 0; i <= v[n-1].h && i <=n ; i++)
if (a[n%2][i] > max)
max = a[n%2][i];
fprintf(fout, "%i", max);
fclose(fin);
fclose(fout);
return 0;
}