Pagini recente » Cod sursa (job #1460479) | Cod sursa (job #2698730) | Cod sursa (job #216351) | Cod sursa (job #2391423) | Cod sursa (job #65453)
Cod sursa(job #65453)
#include <fstream>
using namespace std;
int n;
int m;
long a[17][17],b[17][17] ;
//long a[17][17];
void citire() {
ifstream in("flip.in");
in >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
in >> a[i][j];
a[i][m] = 1;
}
for (int j = 0; j < m; j++)
a[n][j] = 1;
}
long suma(long a[17][17]) {
long s = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (a[n][j] * a[i][m] == 1){
s += a[i][j];
}
else {
s -= a[i][j];
}
return s;
}
long suma_col(int c) {
long s = 0;
for (int i = 0; i < n; i++)
if (a[i][m] == 1){
s += a[i][c];
}
else {
s -= a[i][c];
}
return s;
}
void refac(long b[17][17], long a[17][17]) {
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
a[i][j] = b[i][j];
}
void fac() {
for (int i = 0; i < n; i++)
a[i][m] = 1;
for (int i = 0; i < n; i++)
a[n][i] = 1;
}
void schimba_linie (int l) {
for (int i = 0; i < m; i++)
a[l][i] = -a[l][i];
}
void schimba_coloana (int c) {
for (int i = 0; i < n; i++)
a[i][c] = -a[i][c];
}
//long actiune() {
// long sm = suma(a);
// //refac(a, b);
// long max = (1 << (n + m));
// for (long x = 0; x < max; x++) {
// long s = 0;
// for (int i = 0; i < n; i++)
// if (x & (1 << i))
// // schimba_linie(i);
// a[i][m] = -1;
// for (int i = n; i < n + m; i++)
// if (x & (1 << i))
// // schimba_coloana(i - n);
// a[n][i - n] = -1;
// s = suma(a);
// if (s > sm)
// sm = s;
// //refac(b, a);
// fac();
// }
// return sm;
//}
long actiune(long a[17][17], int n, int m) {
long sm = suma(a);
for (long x = 0; x < (1 << n); x++) {
long s = 0;
for (int i = 0; i < n; i++)
if (x & (1 << i))
a[i][m] = -1;
s = 0;
for (int j = 0; j < m; j++) {
int s1 = suma_col(j);
if (s1 < 0)
a[n][j] = -1;
}
s = suma(a);
if (s > sm)
sm = s;
fac();
}
return sm;
}
void transpusa () {
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
b[i][j] = a[j][i];
}
int main() {
citire();
ofstream out("flip.out");
long s1 = actiune(a, n, m);
transpusa();
long s2 = actiune(b, m, n);
out << (s1 > s2 ? s1 : s2);
out.close();
return 0;
}