Cod sursa(job #461787)

Utilizator piroslPiros Lucian pirosl Data 8 iunie 2010 16:52:07
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>

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

int idxranduri[8000];

long max;

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

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

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

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

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

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

			for(i=1;i<n;++i)
			{
				int a = coloanes[i];
				int poz = i-1;
				while(poz>=0 && coloanes[poz] > a)
				{
					coloanes[poz+1] = coloanes[poz];
					--poz;
				}
				coloanes[poz+1] = a;
			}

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

			if(sum > max)
				max = sum;

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


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

	return 0;
}