Cod sursa(job #567175)

Utilizator Rares95Rares Arnautu Rares95 Data 29 martie 2011 19:51:23
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
	
  # include <fstream>
  # include <cstring>
  # include <algorithm>
	using namespace std;
	
	int n, m, r, c, i, j, sol, ok;
	int s[1001], x[1001];
	short a[1001][1001];
	
	void solve () {
		int sum = 0;
		for ( i = 1; i <= n; ++i )
			for ( j = 1; j <= m; ++j )
				s[j] += a[i][j] * ( !x[i] );
		sort ( s + 1, s + m + 1 );
		for ( i = m; i > c; --i ) sum += s[i];
		if ( sum > sol ) sol = sum;
		memset ( s, 0, sizeof s );
	}
	
	int check () {
		int nr = 0;
		for ( int i = 1; i <= n; ++i ) 
			nr += x[i];
		return ( nr == r );
	}
	
	void back () {
		int k = 1;
		x[1] = -1;
		
		do {
			while ( x[k] < 1 ) {
				++x[k];
				if ( k == n ) {
					if ( check () ) solve ();
				}
				else x[++k] = -1;
			}
			--k;
		} while ( k );
	}
	
	int main () {
		
		ifstream f ( "elimin.in" );
		ofstream g ( "elimin.out");
		
		f >> n >> m >> r >> c;
		
		if ( n <= m ) {
			ok = 1;
			for ( i = 1; i <= n; ++i )
				for ( j = 1; j <= m; ++j )
					f >> a[i][j];
		}
		else {
			for ( i = 1; i <= n; ++i ) 
				for ( j = 1 ; j <= m; ++j ) 
					f >> a[j][i];
			n ^= m ^= n ^= m;
			r ^= c ^= r ^= c;
		}
		
		back ();
		g << sol << '\n';
		
		g.close ();
		return 0;
	}