Pagini recente » Cod sursa (job #2055204) | Cod sursa (job #2055219) | Cod sursa (job #3157486) | Cod sursa (job #2919917) | Cod sursa (job #434494)
Cod sursa(job #434494)
/*
* 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 i, max = 0;
List l, max_l = NULL;
for(i = n; 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;
}
List max_vect(List *v, long int min, long int max){
long int j, maxi = 0;
List max_l = NULL;
for(j = min; j < max; j++){
if(v[j] != NULL)
if (maxi < v[j] -> greutate){
maxi = v[j] -> greutate;
max_l = v[j];
}
}
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, nivel_curent, j;
List *v_max;
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));
v_max = (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;
for (j = nivel_min; j <= nivel_max; j++){
v_max[j] = maxim(vector, j);
}
while (nivel_max >= i){
l = max_vect(v_max, nivel_min, i+1);
nivel_curent = l -> nivel;
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);
}
}
v_max[nivel_curent] = maxim(vector, nivel_curent);
i++;
}
fprintf(fout, "%ld", max);
/*golire(vector, nivel_min, nivel_max);*/
fclose(fin);
fclose(fout);
return 0;
}