Cod sursa(job #434196)

Utilizator IgrecCorina Popescu Igrec Data 5 aprilie 2010 12:21:20
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 2.13 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 100001

typedef struct item {
	long int nivel;
	long int gr;
	item *next;
} item;



void adauga1 (long int v[NMAX], long int val, long int n) {
	v[n] = val;
	long int i=n;
	while ((val < v[i-1]) && (i>0)){
		v[i] = v[i-1];
		v[i-1] = val;
		i--;
	}

}

void adauga2 (long int v[NMAX], long int val, long int n) {
	long int i=1;
	v[1] = val;
	while ((val > v[i+1]) && (i<n)) {
		v[i] = v[i+1];
		v[i+1] = val;
		i++;
	}

}

item * insereaza (item *p, long int j, long int val) {
	
	item *nou = new item; nou->nivel = j; nou->gr = val; nou->next = NULL; //creare element nou

	if ((j < p->nivel) || ((j == p->nivel) && (val > p->gr))) { //daca nivelul e minim si inexistent sau valoare de introdus e pe primul nivel
		nou->next = p;
		p = nou;
		return p;
	}

	item *aux = new item; aux = p;

	while ((aux->next != NULL) && (j > aux->next->nivel))
		aux = aux->next;

	if (aux->next == NULL) { //nivelul pe care vreau sa-l introduc e mai mare decat celelalte
		aux->next = nou;
		return p;
	}

	if (j < aux->next->nivel) { //nivelul nu exista dar nu este cel mai mare
		nou->next = aux->next;
		aux->next = nou;
		return p;
	}

	//nivelul exista
	while ((aux->next->nivel == j) && (val < aux->next->gr))
		aux = aux->next;

	if (aux->next == NULL) { //valoare e cea mai mica de pe cel mai mare nivel
		aux->next = nou;
		return p;
	}
	
	nou->next = aux->next; aux->next = nou;
	return p;
	
}

int main () {

FILE *f, *g;
long int n, hmax, u, h, val, s=0, i, j, v[NMAX];


f = fopen ("gutui.in", "r");
g = fopen ("gutui.out", "w");

fscanf (f, "%ld", &n);
fscanf (f, "%ld", &hmax);
fscanf (f, "%ld", &u);

fscanf (f, "%ld", &h);
fscanf (f, "%ld", &val);

item *p = new item; p->gr = val; p->nivel = (hmax-h)/u + 1;

for (i=2; i<=n; i++) {
	fscanf (f, "%ld", &h);
	fscanf (f, "%ld", &val);
	j = (hmax-h)/u + 1;
	p = insereaza (p, j, val);
}

int index = 0;

while (p != NULL) {
	if (index < p->nivel) {
		s += p->gr;
		index++;
		adauga1 (v, p->gr, index);
	}
	else 
		if (p->gr > v[1]) {
			s = s - v[1] +	p->gr;
			adauga2 (v, p->gr, index);	
		}
	p=p->next;
}

fprintf (g, "%ld", s);
	

fclose (f); fclose (g);

return 0;
}