Pagini recente » Cod sursa (job #110497) | Cod sursa (job #101424) | Cod sursa (job #1933959) | Cod sursa (job #1923341) | Cod sursa (job #567163)
Cod sursa(job #567163)
# include <fstream>
# include <cstring>
# include <algorithm>
using namespace std;
int n, m, r, c, i, j, sol;
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 solve2 () {
int sum = 0;
for ( j = 1; j <= m; ++j )
for ( i = 1; i <= n; ++i )
s[j] += a[j][i] * ( !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 );
}
void back2 () {
int k = 1;
x[1] = -1;
do {
while ( x[k] < 1 ) {
++x[k];
if ( k == n ) {
if ( check () ) solve2 ();
}
else x[++k] = -1;
}
--k;
} while ( k );
}
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 ) {
for ( i = 1; i <= n; ++i )
for ( j = 1; j <= m; ++j )
f >> a[i][j];
back ();
}
else {
for ( i = 1; i <= n; ++i )
for ( j = 1 ; j <= m; ++j )
f >> a[i][j];
n ^= m ^= n ^= m;
r ^= c ^= r ^= c;
back2 ();
}
g << sol << '\n';
g.close ();
return 0;
}