Cod sursa(job #434357)

Utilizator IgrecCorina Popescu Igrec Data 5 aprilie 2010 18:46:01
Problema Gutui Scor 60
Compilator cpp Status done
Runda teme_upb Marime 1.54 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 100001

typedef struct item {
	long int poz;
	long int val;
	item *next;
} item;

item *p, *l;

void adauga (long int j, long int gr) {
	item *nou = new item;
	nou->poz = j; nou->val = gr; nou->next = NULL;
	if (j <= p->poz) {
		nou->next = p; p = nou; return;
	}
	if (j >= l->poz) {
		l->next = nou; l = nou; return;
	}
	item *a, *b; a = p; b = p->next;
	while (j > b->poz) {
		a = b;
		b = b->next;
	}
	nou->next = b;
	a->next = nou;
}

long int minim (long int v[NMAX], long int i, long int j) {
	if (i == j) return i;
	long int m, a, b;
	m = (i+j)/2;
	a = minim (v, i, m); b = minim (v, m+1, j);
	return (v[a] > v[b]) ? b : a;
}

int main () {

FILE *f, *g;
long int n, hmax, u, h, gr, 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", &gr);

p = new item; l = new item;
p->poz = (hmax-h)/u + 1; p->val = gr; p->next = NULL; l = p;

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

long int index = 0;

/*item *aux = new item; aux=p;
while (aux != NULL) {
	printf ("%ld %ld\n", aux->poz, aux->val);
	aux=aux->next;
}*/

while (p != NULL) {
	if (p->poz > index) {
		index++;
		s = s+p->val;
		v[index] = p->val;
		
	}
	else {
		long int k = minim (v, 1, p->poz);
		if (p->val > v[k]) {
			s = s-v[k]+p->val;
			v[k] = p->val;
		}
	}
	p = p->next;
}

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

fclose (f); fclose (g);

return 0;
}