Cod sursa(job #8805)

Utilizator diac_paulPaul Diac diac_paul Data 25 ianuarie 2007 17:24:26
Problema Elimin Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <stdio.h>
#include <stdlib.h>

#define NMin 16
#define NMax 7295
#define Pdoi 257

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


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, k1, k2;

	for (k = 0; k < 1<<m; k++)
	{
		// k = 0 0 0 0 0 0 0 0 0 0
		//     ********* ---------
		//         k2       k1

		k2 = k >> 8;
		k1 = k - (k2 << 8);

		for (j = 0; j < m; j++)
		{
			if (!((1<<j) & k))
			{
				if (j < 8 && !uz[k1]) // intra la k1
				{
					for (i = 0; i < n; i++)
						sp[i][0][k1] += a[j][i];
				}
				else if (!uz[k2]) // intra la k2
				{
					for (i = 0; i < n; i++)
						sp[i][1][k2] += a[j][i];
				}
			}
		}
		uz[k1] = 1;
		uz[k2] = 1;
	}
}

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

	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)
		{
			k2 = k >> 8;
			k1 = k - (k2 << 8);

			for (i = 0; i < n; i++)
			{
				sc[i] = sp[i][0][k1] + sp[i][1][k2];
			}

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