Pagini recente » Cod sursa (job #380882) | Cod sursa (job #791042) | Cod sursa (job #1549704) | Cod sursa (job #2406638) | Cod sursa (job #3162221)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int mat[21][21];
int suma_coloane[17];
int vector_bkt[17];
int n, m;
int answer = -1 * (1 << 31);
void test_suma(){
int rasp_temp = 0;
vector<int> indici_flipped;
for (int i = 1; i <= n; i++){
if (vector_bkt[i] == 1) {
indici_flipped.push_back(i);
}
}
for (int i = 1; i <= m; i++){
int sum = suma_coloane[i];
bool flipped = false;
if (sum < 0) {
sum *= -1;
flipped = true;
}
for (int j = 0; j < indici_flipped.size(); j++){
if (flipped == false)
sum += (mat[indici_flipped[j]][i] * -1) * 2;
else
sum += (mat[indici_flipped[j]][i]) * 2;
}
rasp_temp += sum;
}
answer = max(answer, rasp_temp);
}
void backtracking(int poz){
if (poz == n + 1){
test_suma();
return;
}
for (int i = 0; i <= 1; i++){
vector_bkt[poz] = i;
backtracking(poz + 1);
}
}
int main(){
fin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
fin >> mat[i][j];
suma_coloane[j] += mat[i][j];
}
}
backtracking(1);
fout << answer;
return 0;
}