Pagini recente » Cod sursa (job #2925350) | Cod sursa (job #1654374) | Cod sursa (job #955942) | Monitorul de evaluare | Cod sursa (job #70438)
Cod sursa(job #70438)
#include <fstream>
using namespace std;
int n;
int m;
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];
}
}
long suma(long a[17][17], int n, int m) {
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 a[17][17], int n, int m) {
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;
}
long suma_lin(int l, long a[17][17], int n, int m) {
long s = 0;
for (int j = 0; j < m; j++)
if (a[n][j] == 1){
s += a[l][j];
}
else {
s -= a[l][j];
}
return s;
}
void fac(long a[17][17], int n, int m) {
for (int i = 0; i < n; i++)
a[i][m] = 1;
for (int i = 0; i < m; i++)
a[n][i] = 1;
}
long actiune(long a[17][17], int n, int m) {
long sm = suma(a, n, m);
fac(a, n, m);
if (n > m) {
// linii
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;
for (int j = 0; j < m; j++) {
int s1 = suma_col(j, a, n, m);
if (s1 < 0)
a[n][j] = -1;
}
s = suma(a, n, m);
if (s > sm)
sm = s;
fac(a, n, m);
}
return sm;
}
//coloane
for (long x = 0; x < (1 << m); x++) {
long s = 0;
for (int j = 0; j < m; j++)
if (x & (1 << j))
a[n][j] = -1;
for (int i = 0; i < n; i++) {
int s1 = suma_lin(i, a, n, m);
if (s1 < 0)
a[i][m] = -1;
}
s = suma(a, n, m);
if (s > sm)
sm = s;
fac(a, n, m);
}
return sm;
}
int main() {
citire();
ofstream out("flip.out");
out << actiune(a, n, m);
out.close();
return 0;
}