Cod sursa(job #434441)

Utilizator MatwixGherasim Alin Matwix Data 5 aprilie 2010 22:22:21
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 2.16 kb
/*
 * gutui.c
 *
 *  Created on: Apr 4, 2010
 *      Author: matwix
 */

#include <stdio.h>
#include <stdlib.h>

typedef struct list_el {
   long int inaltime, greutate, nivel;
   struct list_el * next, * prev;
} * List;

List maxim(List *v, long int n, long int min){
	long int i, max = 0;
	List l, max_l = NULL;
		for(i = min; i <= n; i++){
			l = v[i];
			while (l != NULL){
				if (l -> greutate > max){
					max = l -> greutate;
					max_l = l;
				}
				l = l -> next;
			}
		}
	return max_l;
}

void print(List l){
	while(l != NULL){
		printf("%ld ", l -> greutate);
		l = l-> next;
	}
}

/*void golire(List* v, long int min, long int max){
	long int i;
	List l, aux;
		for(i = min; i <= max; i++){
			l = v[i];
			while(l != NULL){
				v[l -> nivel] = l -> next;
				aux = l;
				if (l -> next != NULL)
					l -> next -> prev = NULL;
				l = l -> next;
				free(aux);
			}
		}
}*/

int main(){
	long int n, max = 0, H, U, aux1, aux2, i, nivel_max, nivel_min=2147000000;
	FILE *fin = fopen("gutui.in", "r");
	FILE *fout = fopen("gutui.out", "w");
	List *vector;
	List l;

	fscanf (fin, "%ld %ld %ld", &n, &H, &U);

	nivel_max = H/U;

	vector = (List*)malloc((H/U+1)*sizeof(List));

	for (i = 0; i < n; i++){
		fscanf(fin, "%ld %ld", &aux1, &aux2);
		l = (List)malloc(sizeof(struct list_el));
		l -> inaltime = aux1;
		l -> greutate = aux2;
		l -> nivel = H/U - (H-aux1)/U;
		if(l -> nivel < nivel_min)
			nivel_min = l ->nivel;
		if (vector[l -> nivel] != NULL){
			l -> prev = NULL;
			l -> next = vector[l -> nivel];
			vector[l -> nivel] -> prev = l;
			vector[l -> nivel] = l;
		}else{
			l -> prev = NULL;
			l -> next = NULL;
			vector[l -> nivel] = l;
		}
	}

	i = nivel_min;

	while (nivel_max >= i){
		l = maxim(vector, i, nivel_min);
		max += l -> greutate;
		if (l -> prev == NULL){
			vector[l -> nivel] = l -> next;
			if (l -> next != NULL)
				l -> next -> prev = NULL;
			free(l);
		}else{
			if (l -> next == NULL){
				l -> prev -> next = NULL;
				free(l);
			}else{
				l -> prev -> next = l -> next;
				l -> next -> prev = l -> prev;
				free(l);
			}
		}
		i++;
	}

	fprintf(fout, "%ld", max);

	/*golire(vector, nivel_min, nivel_max);*/

	fclose(fin);
	fclose(fout);

	return 0;
}