Cod sursa(job #433583)

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

#define NMAX 10000

typedef struct item {
	long int poz;
	long int v[NMAX];
	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++;
	}

}

void insereaza (long int v[NMAX], long int gr, long int n) {
	if (gr < v[n]) return;
	int i = n-1;
	v[0] = v[0] - v[n] + gr;
	for (i=n; i>=1; i--) {
		if (gr < v[i-1]) break;
		v[i]=v[i-1];
	}
	v[i]=gr;
		
}

void insereaza_gutuie (item *p, long int poz, long int gr) {
	
	if (poz < p->poz) {
		item *nou = new item;
		nou->poz = poz;
		nou->v[0] = nou->v[1] = gr;
		nou->next = p; nou = p;
		return;
	}

	if (poz == p->poz) {
		insereaza (p->v, gr, p->poz);
		return;
	}
	
	item *aux = p;

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

	if (poz == aux->poz) 
		insereaza (aux->v, gr, aux->poz); 
	else if (aux->next == NULL) {
		item *nou = new item;
		nou->poz = poz; nou->v[0] = nou->v[1] = gr;
		nou->next = NULL; aux->next = nou;	
	}
	else {
		item *nou = new item;
		nou->poz = poz; nou->v[0] = nou->v[1] = gr;
		nou->next = aux->next; aux->next = nou;		
	}

}

int main () {

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


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

item *p, *aux;
p = new item; aux = new item;

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

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

j = (hmax-h)/u + 1;
p->poz = j; p->v[0] = p->v[1] = gr;



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

int index = 0;
while (p != NULL) {
	i=1;
	while ((index<p->poz) && (p->v[i] != 0)) {
		s += p->v[i];
		index++;
		adauga1(val, p->v[i], index);
		i++;
	}
	while (p->v[i] > val[1]) {
		s = s-val[1]+p->v[i];
		adauga2(val, p->v[i], index);
		i++;
	}
	p=p->next;
}

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

fclose (f); fclose (g);

return 0;
}