Cod sursa(job #971559)

Utilizator marius135Dumitran Adrian Marius marius135 Data 9 iulie 2013 16:45:04
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
#include<string.h>
#include<iostream>

using namespace std;


int mat[10000][20];


int main() {
	
	int n, m;
	int C, R;
	
	freopen("elmin.in", "r", stdin);
	freopen("elmin.out", "w", stdout);
	
	cin>>n>>m>>R>>C;
	
	if ( n > m ) 
		for( int i = 1; i <= n; ++i)
			for( int j = 1; j <= m; ++j) 
				cin>>mat[i][j];
	
	else  {
		for( int i = 1; i <= n; ++i)
			for( int j = 1; j <= m; ++j)
				cin>>mat[j][i];
		m = m ^ n ^ ( n = m);
		C = R - C + ( R = C);
		
		
	}
	// numarul de coloane va fi mai mic
	
	int optim = -1000000000;
	for( int i = 0; i < ( 1<< m); ++i) {
		int nr = 0;
		for( int j = 0; j < m; ++j)
			nr += !!((1<<j) & i);
		if( nr != C)
			continue;
		
		int sum_lin[5000];
		memset(sum_lin, 0, sizeof(sum_lin));
		for( int j = 1; j <= n; ++j){
			for( int k = 1; k <= m; ++k)
				if( ((1<<(k-1)) & i) == 0)
					sum_lin[j - 1] += mat[j][k];
		}
		sort( sum_lin , sum_lin + n );
		int rez = 0;
		for( int j = R; j < n; ++j)
			rez += sum_lin[j];
		if( rez > optim)
			optim = rez;
	}
	cout<<optim;
	
	
	
	return 0;
}