Cod sursa(job #460926)

Utilizator piroslPiros Lucian pirosl Data 4 iunie 2010 18:11:57
Problema Submultimi Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <stdio.h>

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

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

long max;
long suma;


void verifica()
{
	int i;
	long q = suma;
	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 > max)
		max = q;
}

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)
	{
		int c = 0;
		for(int j=0;j<n;++j)
		{
			scanf("%d ", &matrice[i][j]);
			suma += matrice[i][j];
		}
	}

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

	int rand = 0;
	idxranduri[0] = 0;
	while(idxranduri[0] < m)
	{
		if(idxranduri[rand] < m)
		{
			++rand;
			idxranduri[rand] = idxranduri[rand-1];
		}
		else
			--rand;

		if(rand >= r) 
		{
			for(i=0; i<m; ++i)
				coloanes[i] = coloane[i];
	
			for(i=0;i<r;++i)
			{
				for(int j=0;j<m;++j)
					coloanes[j] -= matrice[idxranduri[i]][j];
			}

			for(i=m-1;i>0;--i)
			{
				for(int j=0;j<i;++j)
				{
					if(coloanes[j] > coloanes[j+1])
					{
						int t = coloanes[j];
						coloanes[j] = coloanes[j+1];
						coloanes[j+1] = t;
					}
				}
			}

			int sum = 0;
			for(i=c;i<m;++i)
				sum += coloanes[i];

			if(sum > max)
				max = sum;
		}
		++idxranduri[rand];
	}


	printf("%ld\n", max);

	return 0;
}