Cod sursa(job #426325)

Utilizator stefanrStefan Ruseti stefanr Data 26 martie 2010 19:13:16
Problema Gutui Scor 80
Compilator c Status done
Runda teme_upb Marime 1.03 kb
#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;
}