Pagini recente » Cod sursa (job #186537) | Cod sursa (job #156275) | Cod sursa (job #2714039) | Cod sursa (job #2125039) | Cod sursa (job #2676973)
#include <fstream>
#include <algorithm>
using namespace std;
const int DIV_MAX = 15;
const int NMAX = 7294;
int a[DIV_MAX][NMAX];
int col[NMAX];
int ord[NMAX];
int n, m, r, c;
int st[DIV_MAX + 1];
int maxy = 0;
int sum_all ( int m ) {
int s = 0;
for ( int i = 0; i < m; i++ )
s += col[i];
return s;
}
bool cmp ( int a, int b ) {
return col[a] < col[b];
}
void bkt ( int k ) {
if ( k == r + 1 ) {
nth_element ( ord, ord + c, ord + m, cmp );
int s = sum_all ( m ), smin = 0;
for ( int i = 0; i < c; i++ )
smin += col[ord[i]];
maxy = s - smin > maxy ? s - smin : maxy;
return;
}
for ( int i = st[k - 1] + 1; i < n - (r - k); i++ ) {
st[k] = i;
for ( int j = 0; j < m; j++ )
col[j] -= a[i][j];
bkt ( k + 1 );
for ( int j = 0; j < m; j++ )
col[j] += a[i][j];
}
}
ifstream fin ( "elimin.in" );
ofstream fout ( "elimin.out" );
int main() {
int i, j, aux;
fin >> n >> m >> r >> c;
if ( n < m ) {
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; j++ )
fin >> a[i][j];
} else {
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; j++ )
fin >> a[j][i];
aux = n, n = m, m = aux;
aux = r, r = c, c = aux;
}
for ( i = 0; i < m; i++ )
ord[i] = i;
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; j++ )
col[j] += a[i][j];
st[0] = -1;
bkt ( 1 ); // nu am facut cu descompunerea in baza 2 deoarece
// trebuia sa verificam pt fiecare indice nr de biti 1
fout << maxy;
return 0;
}