Pagini recente » Cod sursa (job #348067) | Cod sursa (job #2578970) | Cod sursa (job #2970034) | Cod sursa (job #2988154) | Cod sursa (job #3003631)
/*
Generam toate posibilitatile de flip pentru coloane:
1. Ele sunt siruri de 0 si 1 de lungime m <=>
Un numar in baza 2 cu m biti <=> Un numar in baza 10
m = 3
000 => 0
001 => 1
010 => 2
011 => 3
100 => 4
101 => 5
110 => 6
111 => 7
Operatii pe biti:
// 1. << (shift left): (0101 << 1) = 01010 | (x << k) <=> (2^k) * x
// 2. & (AND): 100101001 &
// 110011000 =
// 100001000
// Cum stim daca bitul p al numarului x (in baza 10) este 1 sau 0?
// x = 101101001 &
// p = 3 => (1<<p) = 000001000
// 000001000 > 0 ?
// ((1<<p) & x) > 0 => DA
// 3. | (OR): 100101001 |
// 110011000 =
// 110111001
// 4. ^ (XOR): 100101001 |
// 110011000 =
// 010110001
// 5. >> (shift right) => 1010110101 >> 4 = 0000101011
// x >> k => x / (2^k) (fara rest)
*/
#include <fstream>
#include <vector>
#include <climits>
using namespace std;
vector<int> coloane;
int n, m, a[20][20], sol = -INT_MAX;
ifstream fin("flip.in");
ofstream fout("flip.out");
void flip_col(int col) {
for(int lin = 1; lin <= n; lin++) {
a[lin][col] *= -1;
}
}
int main() {
fin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
fin >> a[i][j];
}
}
for(int mask = 0; mask < (1 << m); mask++) { // 1 << m = 2^m
// mask e numar in baza 10
// trebuie sa il traducem in baza 2 ca sa aflam subsetul de coloane flipuite
for(int bit = 0; bit < m; bit++) {
if(((1<<bit)&mask) > 0) {
// Bitul bit e 1 => Coloana (bit + 1) va fi flipuita
flip_col(bit + 1);
}
}
int total = 0;
for(int lin = 1; lin <= n; lin++) {
int sum = 0;
for(int j = 1; j <= m; j++) {
sum += a[lin][j];
}
total += abs(sum);
}
sol = max(sol, total);
// Undo
for(int bit = 0; bit < m; bit++) {
if(((1<<bit)&mask) > 0) {
// Bitul bit e 1 => Coloana (bit + 1) va fi flipuita
flip_col(bit + 1);
}
}
}
fout << sol << "\n";
return 0;
}