Cod sursa(job #8795)

Utilizator diac_paulPaul Diac diac_paul Data 25 ianuarie 2007 16:46:22
Problema Elimin Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#include <stdlib.h>

#define NMin 16
#define NMax 7295

FILE *fin, *fout;
long n, m, r, c, a[NMin][NMax];
long sl[NMax], sc[NMax], maxt;

void citire()
{
	long i, j;

	fin = fopen("elimin.in", "rt");

	fscanf(fin, "%ld %ld %ld %ld", &m, &n, &r, &c);

	if (m > n)
	{
		for (i = 0; i < m; i++)
			for (j = 0; j < n; j++)
				fscanf(fin, "%ld", & a[j][i]);
		i = m; m = n; n = i;
		i = r; r = c; c = i;
	}
	else
	{
		for (i = 0; i < m; i++)
			for (j = 0; j < n; j++)
				fscanf(fin, "%ld", & a[i][j]);
	}
	fclose(fin);
}

void preprocesare()
{
	long i, j, k;

	/*for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
		{
			sl[i] += a[i][j];
			sc[j] += a[i][j];
		}*/
}

int comp(const void *a, const void *b)
{
	return (*(long*)a)-(*(long*)b);
}
void bkt()
{
	long i, j, k, nr;

	for (k = 0; k < 1<<m; k++) // bitii lui k reprezinta randurile pe care le scot
	{
		nr = 0;
		for (j = 1; j < 1<<m; j*=2)
		{
			if (j & k) nr++;
		}

		if (nr == r)
		{
			for (i = 0; i < n; i++) sc[i] = 0;

			for (j = 0; j < m; j++)
				if (!((1<<j) & k))
				{
					// randul j nu a fost eliminat
					for (i = 0; i < n; i++)
					{
						sc[i] += a[j][i];
					}
				}
			qsort(sc, n, sizeof(sc[0]), comp);

			nr = 0;
			for (i = c; i < n; i++)
				nr+= sc[i];

			if (nr > maxt)
				maxt = nr;

		}
	}
}

void afisare()
{
	fout = fopen("elimin.out", "wt");
	fprintf(fout, "%ld\n", maxt);
	fclose(fout);
}

int main()
{
	citire();
	preprocesare();
	bkt();
	afisare();
	return 0;
}