Pagini recente » Cod sursa (job #597649) | Cod sursa (job #1375456) | Cod sursa (job #2304131) | Cod sursa (job #2303146) | Cod sursa (job #1010816)
#include <fstream>
#include <bitset>
using namespace std;
int mat[16][16];
int N, M, MAX;
bitset<16> sol;
void input() {
ifstream in("flip.in");
in>>N>>M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
in>>mat[i][j];
MAX += mat[i][j];
}
}
in.close();
}
void coloane(int total) {
for (int j = 0; j < M; ++j) {
int sum = 0;
for (int i = 0; i < N; ++i) {
sum += (sol[i] == 0 ? mat[i][j] : -mat[i][j]);
}
if (total - 2*sum > MAX) {
MAX = total = total - 2*sum;
}
}
}
void back(int k, int total) {
if (k == N) {
return;
}
//sol[k] = 0:
coloane(total);
back(k + 1, total);
//sol[k] = 1:
sol[k] = 1;
int suma = 0;
for (int i = 0; i < M; ++i) {
suma += mat[k][i];
}
coloane(total - 2*suma);
back(k + 1, total - 2*suma);
sol[k] = 0;
}
void solve() {
back(0, MAX);
}
void output() {
ofstream out("flip.out");
out<<MAX;
out.close();
}
int main() {
input();
solve();
output();
return 0;
}