Cod sursa(job #461825)

Utilizator piroslPiros Lucian pirosl Data 8 iunie 2010 18:12:11
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <stdlib.h>

void sort(int* array, int inc, int sf)
{
	if(sf - inc <= 1)
		return;

	int i = inc;
	int s = sf;
	int poz = i;
	while(i<s) 
	{
		while(poz < s && array[poz] <= array[s])
			--s;
		if(poz < s)
		{
			int t = array[s];
			array[s] = array[poz];
			array[poz] = t;
			poz = s;
			while(poz > i && array[poz] >= array[i])
				++i;

			if(poz > i)
			{
				int t = array[i];
				array[i] = array[poz];
				array[poz] = t;
				poz = i;
			}
			else
			{
				sort(array, inc, poz - 1);
				sort(array, poz+1, sf);
			}
		}
		else
		{
			sort(array, inc, poz - 1);
			sort(array, poz+1, sf);
		}
	}
}

int main(void)
{
	int m,n, r, c;
	int* matrice;
	int* coloane;
	int* coloanes;
		
	int* idxranduri;
	
	long max = 0;

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

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

	matrice = (int*)malloc(m*n*sizeof(int));

	int i;
	if(m<=n) 
	{
		for(i=0;i<m;++i)
		{
			for(int j=0;j<n;++j)
			{
				scanf("%d ", matrice+n*i+j);
			}
		}
	}
	else 
	{
		for(i=0;i<m;++i)
		{
			for(int j=0;j<n;++j)
			{
				scanf("%d ", matrice+i+m*j);
			}
		}

		int t = m;
		m = n;
		n = t;
		t = r;
		r = c;
		c = t;
	}

	coloane = (int*)malloc(n*sizeof(int));
	coloanes = (int*)malloc(n*sizeof(int));
	idxranduri = (int*)malloc((r+1)*sizeof(int));

	for(i=0;i<n;++i)
		coloane[i] = 0;

	for(i=0;i<m;++i)
	{
		for(int j=0;j<n;++j)
		{
			coloane[j] += matrice[n*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) 
		{
			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[n*idxranduri[i]+j];
			}

			sort(coloanes, 0, n-1);

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

			if(sum > max)
				max = sum;

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

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

	free(matrice);
	free(coloane);
	free(coloanes);
	free(idxranduri);

	return 0;
}