Cod sursa(job #7112)

Utilizator peanutzAndrei Homorodean peanutz Data 21 ianuarie 2007 12:32:15
Problema Elimin Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.54 kb
#include <stdio.h>

#define NMAX 550

typedef struct stiva
{
int nr, val;
};

long lin[NMAX], col[NMAX];
long a[NMAX][NMAX];
long n, m, r, c;
long suma, h2;
long min = 2000000000;
long uzc[NMAX], uzl[NMAX], h = 0, plus, sol;


long flinie[NMAX];
long fcoloana[NMAX];


void read()
{
long i, j, x;

scanf("%ld %ld %ld %ld\n", &n, &m, &r, &c);


for(i = 1; i <= n; ++i)
	{

		for(j = 1; j <= m; ++j)
			{
				scanf("%ld ", &a[i][j]);

				lin[i] += a[i][j];
				col[j] += a[i][j];

				suma += a[i][j];
			}
		scanf("\n");
	}
}



void back(long linii, long coloane)
{
long i, for1, for2, j;


if(linii == r  &&  coloane == c)
	{
		for(for1 = plus = 0; for1 < h; ++for1)
			for(for2 = 0; for2 < h2; ++for2)
				plus += a[uzl[for1]][uzc[for2]];


		if(min > sol-plus)
			min = sol-plus;
	}

else
	{
		for(i = 1; i <= n; ++i)
			{
				if(linii < r && !flinie[i])
				{
					sol += lin[i];

					uzl[h++] = i;

					flinie[i] = 1;


					back(linii+1, coloane);

					--h;
					sol -= lin[i];

					flinie[i] = 0;
				}
			}
		for(j = 1; j <= m; ++j)
			{
				if(coloane < c  &&  !fcoloana[j])
				{
					sol += col[j];

					uzc[h2++] = j;

					fcoloana[j] = 1;

					back(linii, coloane+1);

					sol -= col[j];
					fcoloana[j] = 0;
					--h2;
				}

			}
	}
}


int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);


read();


back(0, 0);


printf("%ld\n", suma-min);



fclose(stdin);
fclose(stdout);


return 0;
}