Cod sursa(job #433453)

Utilizator IgrecCorina Popescu Igrec Data 3 aprilie 2010 18:31:29
Problema Gutui Scor 60
Compilator c Status done
Runda teme_upb Marime 1.55 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 1000

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 a[NMAX][NMAX], long int val, long int i, long int j) {
	int k;
	a[0][j] = a[0][j] - a[j][j] + val;
	for (k=j; k>=i; k--)
		a[k][j] = a[k-1][j];
	a[i][j] = val;
}

void insereaza_gutuie (long int a[NMAX][NMAX], long int val, long int j) {

	if (val < a[j][j]) return;

	if (a[0][j] == 0) {
		a[0][j] = val;
		a[1][j]=val;
		return;
	}
	
	long int i;

	for (i=1; i<=j; i++)
		if (val > a[i][j]) {
			insereaza (a, val, i, j);
			break;
		}
}

int main () {

FILE *f, *g;
long int i, j, n, hmax, u, a[NMAX][NMAX], s=0, index=0, h, gr, indice=0, 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", &gr);
	j = (hmax-h)/u + 1;
	if (j > indice)
		indice = j;
	insereaza_gutuie (a, gr, j);
}

for (j=1; j<=indice; j++) {
	while (a[0][j] == 0)
		j++;
	i=1;
	while ((index<j) && (a[i][j] != 0)) {
		s += a[i][j];
		index++;
		adauga1(v, a[i][j], index);
		i++;
	}
	while (a[i][j] > v[1]) {
		s = s-v[1]+a[i][j];
		adauga2(v, a[i][j], index);
		i++;
	}
}



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

fclose (f); fclose (g);

return 0;
}