Cod sursa(job #425728)

Utilizator stefanrStefan Ruseti stefanr Data 25 martie 2010 23:55:17
Problema Gutui Scor 10
Compilator c Status done
Runda teme_upb Marime 1.78 kb
#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;
}