Cod sursa(job #436836)

Utilizator LP337Lazar Pavel LP337 Data 8 aprilie 2010 23:53:54
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.71 kb
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

void printMat(int **mat, int n, int m){
	for( int i = 0; i < n; i++ ){
		for ( int j = 0; j < m; j++ ){
			printf("%d ",mat[i][j]);
		}
		printf("\n");
	}
}
int getMax(int *m,int n){
	int max = 0;
	for( int i = 0; i < n; i++){
		if( max < m[i] ) 
			max = m[i];
	}
	return max;
}

int maxW(int **matG, int nG, int sum, int k, int h, int u){
	int **mat = (int**)malloc(sizeof(int*));
	int *m = (int*)malloc(sizeof(int));
	int cm = 0;
	int cmat = 0;
	int maxH = 0;
	int G = 0;
	int pos;
	
	if( nG == 0 ){
		//printf("-->%d\n",sum);
		return sum;
	}

	for( int i = 0; i < nG; i++ ){
		if( matG[i][0] + k*u > h ){
			m[cm] = matG[i][1];
			cm++;
			m = (int*)realloc(m,(cm+1)*sizeof(int));
		}else{
			if( i == nG-1 && cm == 0){
				sum = sum + matG[i][1];
			}else{
				mat[cmat] = (int*)malloc(2*sizeof(int));
				mat[cmat][0] = matG[i][0];
				mat[cmat][1] = matG[i][1];
				cmat++;
				mat = (int**)realloc(mat,(cmat+1)*sizeof(int*));
			}
		}
	}

	sum = sum + getMax(m,cm);
	//printf("%d %d\n",sum,cmat);
	k++;
	return maxW(mat,cmat,sum,k,h,u);
}

int main(){
	FILE* fin = fopen("gutui.in","r");
	FILE* fout = fopen("gutui.out","w");
	
	int nG,h,u,**matGt;
	int i;
	int sum;
	
	fscanf(fin,"%d%d%d",&nG,&h,&u);
	
	matGt = (int**)malloc(nG*sizeof(int*));
	for( i = 0; i < nG; i++ ){
		matGt[i] = (int*)malloc(2*sizeof(int));
	}
	
	for( i = 0; i < nG; i++ ){
		fscanf(fin,"%d%d",&matGt[i][0],&matGt[i][1]);
	}
	
	/*
	printf("%d %d %d\n",nG,h,u);
	printMat(matGt,nG,2);
	*/
	
	sum = maxW(matGt,nG,0,0,h,u);
	
	fprintf(fout,"%d",sum);
	
	fclose(fin);
	fclose(fout);
	//system("pause");
	return 0;
}