Cod sursa(job #2695567)

Utilizator euyoTukanul euyo Data 13 ianuarie 2021 18:57:50
Problema Elimin Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin( "elimin.in" );
ofstream fout( "elimin.out" );

const int LimUp = 7295;
const int LimDw = 20;

int A[LimUp][LimDw];
int B[LimDw][LimUp];
int v[LimDw];
int s[LimDw];
int f[LimDw];

int n, m, x, y, q;

int getMax1( int k ) {
  for ( int i = 0; i < m; ++i ) {
    f[i] = 0;
  }
  for ( int i = 1; i <= k; ++i ) {
	f[v[i] - 1] = 1;
  }
  for ( int i = 0; i < n; ++i ) {
	s[i] = 0;
	for ( int j = 0; j < m; ++j ) {
	  if ( !f[j] ) {
		s[i] += A[i][j];
	  }
	}
  }
  sort( s, s + n );
  int res = 0;
  for ( int i = x; i < n; ++i ) {
	res += s[i];
  }
  return res;
}

int getMax2( int k ) {
  for ( int i = 0; i < n; ++i ) {
    f[i] = 0;
  }
  for ( int i = 1; i <= k; ++i ) {
	f[v[i] - 1] = 1;
  }
  for ( int j = 0; j < m; ++j ) {
	s[j] = 0;
	for ( int i = 0; i < n; ++i ) {
	  if ( !f[i] ) {
		s[j] += B[i][j];
	  }
	}
  }
  sort( s, s + m );
  int res = 0;
  for ( int i = y; i < m; ++i ) {
	res += s[i];
  }
  return res;

}

int h = 0;

void elim( int n, int k, int pos, int t ) {
  int a;
 
  if ( pos > k ) {
	if ( t == 0 ) {
      a = getMax1( k );
	} else {
      a = getMax2( k );
	}
	h = h < a ? a : h;
  } else {
    for ( v[pos] = v[pos - 1] + 1; v[pos] <= n - (k - pos); ++v[pos] ) {
      elim( n, k, pos + 1, t );
    }
  }
}

int main() {
  fin >> n >> m >> x >> y;
  if ( n > m ) {
	for ( int i = 0; i < n; ++i ) {
	  for ( int j = 0; j < m; ++j ) {
		fin >> A[i][j];
	  }
    }
	//coloane
	v[0] = 0;
	elim( m, y, 1, 0 );
	fout << h;
  } else {
    for ( int i = 0; i < n; ++i ) {
	  for ( int j = 0; j < m; ++j ) {
		fin >> B[i][j];
	  }
    }
	//linii
	v[0] = 0;
	elim( n, x, 1, 1 );
	fout << h;
  }
  fin.close();
  fout.close();
  return 0;
}