Cod sursa(job #433584)

Utilizator IgrecCorina Popescu Igrec Data 3 aprilie 2010 21:42:34
Problema Gutui Scor 60
Compilator cpp Status done
Runda teme_upb Marime 1.46 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 1000

void adauga1 (int v[NMAX], int val, int n) {
	v[n] = val;
	int i=n;
	while ((val < v[i-1]) && (i>0)){
		v[i] = v[i-1];
		v[i-1] = val;
		i--;
	}
}

void adauga2 (int v[NMAX], int val, int n) {
	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 (int a[NMAX][NMAX], int val, int i, int j) {

	a[0][j] = a[0][j] - a[j][j] + val;
	for (int k=j; k>=i; k--)
		a[k][j] = a[k-1][j];
	a[i][j] = val;
}

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

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

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

int main () {

FILE *f, *g;
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, "%d", &n);
fscanf (f, "%d", &hmax);
fscanf (f, "%d", &u);


for (i=1; i<=n; i++) {
	fscanf (f, "%d", &h);
	fscanf (f, "%d", &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, "%d", s);
	

fclose (f); fclose (g);

return 0;
}