Pagini recente » Cod sursa (job #2540395) | Cod sursa (job #3264017) | Borderou de evaluare (job #2488558) | Borderou de evaluare (job #1165362) | Cod sursa (job #3279132)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main() {
ifstream fin("flip.in");
ofstream fout("flip.out");
int N, M;
fin >> N >> M;
vector<vector<int>> board(N, vector<int>(M));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
fin >> board[i][j];
int maxSum = -INF;
// Parcurgem toate combina?iile de liniile care pot fi inversate (2^N posibilita?i)
for (int mask = 0; mask < (1 << N); mask++) {
vector<vector<int>> temp = board;
// Aplicam inversarea liniilor conform bitmask-ului
for (int i = 0; i < N; i++) {
if (mask & (1 << i)) { // Linia i trebuie inversata
for (int j = 0; j < M; j++) {
temp[i][j] *= -1;
}
}
}
// Decidem optim asupra coloanelor
int sum = 0;
for (int j = 0; j < M; j++) {
int colSum = 0;
for (int i = 0; i < N; i++) {
colSum += temp[i][j];
}
// Daca suma coloanei este negativa, o inversam
if (colSum < 0) {
colSum *= -1;
}
sum += colSum;
}
// Actualizam suma maxima
maxSum = max(maxSum, sum);
}
fout << maxSum << "\n";
return 0;
}