Pagini recente » Cod sursa (job #3216530) | Cod sursa (job #1415328) | Cod sursa (job #3254984) | Cod sursa (job #2671729) | Cod sursa (job #434441)
Cod sursa(job #434441)
/*
* 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;
}