Cod sursa(job #460914)

Utilizator piroslPiros Lucian pirosl Data 4 iunie 2010 17:10:15
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 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];

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];
			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];
		}
		coloane[j] = c;
	}

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

		if(rand >= r) 
		{
			idxcoloane[0] = 0;
			int coloana = 0;
			while(idxcoloane[0] < n-c)
			{
				if(idxcoloane[coloana] < n)
				{
					++coloana;
					idxcoloane[coloana] = idxcoloane[coloana-1];
				}
				else
					--coloana;

				if(coloana >= c)
				{
					//verifica();
					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;

					--coloana;
				}
				++idxcoloane[coloana];
				
			}
			--rand;
		}
		++idxranduri[rand];
	}

//	procranduri(0, 0);

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

	return 0;
}