Cod sursa(job #434336)

Utilizator IgrecCorina Popescu Igrec Data 5 aprilie 2010 17:38:45
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 100001

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 nivel[NMAX], long int gr[NMAX], long int j, long int val, int n) {
	while (j < nivel[n-1]) {
		nivel[n] = nivel[n-1];
		gr[n] = gr[n-1];
		n--;
	}

	
	nivel[n] = j;
	gr[n] = val;
}

long int adauga (long int v[NMAX], long int n, long int val) {
	long int minim = 0, minus;
	v[0] = val;
	long int i;
	for (i=n; i>0; i--) {
		if (v[i] == 0) {
			v[i] = val; return 0;
		}
		if (v[i] < v[minim]) {
			minim = i;
		}
	}
	minus = v[minim]; v[minim] = val;
	return minus;
}

int main () {

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


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

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

for (i=1; i<=n; i++) {
	fscanf (f, "%ld", &h);
	fscanf (f, "%ld", &val);
	j = (hmax-h)/u + 1;
	s = s+val;
	if (v[j] == 0) {
		v[j] = val;
	}
	else {
		s = s - adauga (v, j, val);
	}
}


int index = 0;

for (i=1; i<=n; i++) {
	if (index < nivel[i]) {
		s += gr[i];
		index++;
		adauga1 (v, gr[i], index);
	}
	else 
		if (gr[i] > v[1]) {
			s = s - v[1] +	gr[i];
			adauga2 (v, gr[i], index);	
		}
		
	
}

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

fclose (f); fclose (g);

return 0;
}