Cod sursa(job #434195)

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

#define NMAX 100001

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

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--;
	}

	while ((j == nivel[n-1]) && (val > gr [n-1])) {
		nivel[n] = nivel[n-1];
		gr[n] = gr[n-1];
		n--;
	}
	nivel[n] = j;
	gr[n] = val;
}

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;
	insereaza (nivel, gr, j, val, i);
}


int index = 0;

for (i=1; i<=n; i++) {
	if (index < nivel[i]) {
		s += gr[i];
		index++;
		v[index] = gr[i];
	}
	else 
	{
		long int k = minim (v, 1, index);
		if (v[k] < gr[i]) {
			s = s - v[k] +	gr[i];
			v[k] = gr[i];	
		}
	}
		
	
}

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

fclose (f); fclose (g);

return 0;
}