Cod sursa(job #460432)

Utilizator piroslPiros Lucian pirosl Data 2 iunie 2010 16:32:24
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <stdio.h>

int m,n, r, c;
int matrice[8000][8000];
int coloane[8000];
int randuri[8000];

int idxcoloane[8000];
int idxranduri[8000];

int min;
int suma;


void verifica()
{
	int i;
	int q = 0;
	for(i=0;i<r;++i)
		q += randuri[idxranduri[i]];
	for(i=0;i<c;++i)
		q += coloane[idxcoloane[i]];
	for(i=0;i<r;++i)
	{
		for(int j=0;j<c;++j)
			q -= matrice[idxranduri[i]][idxcoloane[j]];
	}
	if(q < min)
		min = q;
}

void proccoloane(int i, int p)
{
	if(p == c)
	{
		verifica();
		return;
	}
	for(int j=i; j<m;++j) 
	{
		idxcoloane[p] = j;
		proccoloane(i+1, p+1);
	}
}

void procranduri(int i, int p)
{
	if(p == r)
	{
		proccoloane(0,0);
		return;
	}
	for(int j=i; j<m;++j) 
	{
		idxranduri[p] = j;
		procranduri(i+1, p+1);
	}
}

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

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

	int i;
	suma = 0;
	for(i=0;i<m;++i)
	{
		for(int j=0;j<n;++j)
		{
			scanf("%d ", &matrice[i][j]);
			suma += matrice[i][j];
		}
	}

	for(i=0;i<m;++i)
	{
		int c = 0;
		for(int j=0;j<n;++j)
		{
			c += matrice[i][j];
		}
		randuri[i] = c;
	}

	for(int j=0;j<n;++j)
	{
		int c = 0;
		for(int i=0;i<m;++i)
		{
			c += matrice[i][j];
		}
	}

	min = 999999999;
	procranduri(0, 0);

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

	return 0;
}