Pagini recente » Cod sursa (job #930369) | Cod sursa (job #2829453) | Cod sursa (job #706522) | Cod sursa (job #2208495) | Cod sursa (job #2908239)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("flip1.in");
ofstream out("flip.out");
int **matrix;
int *colSwitch;
int n,m;
int maxSum = 0;
void read(){
in >> n>>m;
matrix = new int*[n];
for(int i = 0 ; i < n ;i ++){
matrix[i] = new int[m];
for(int j = 0 ; j < m ; j ++){
in >> matrix[i][j];
}
}
colSwitch = new int[m];
}
int solve(){
int sum = 0 ;
for(int i = 0 ; i < n ; i ++){
int rowSum = 0;
for(int j = 0 ; j < m ; j ++){
rowSum += colSwitch[j] * matrix[i][j];
}
// max(+/- colsum) = abs (rowSum)
int x = abs(rowSum);
sum+=x;
}
return sum;
}
void backtrack(int row){
if(row == m){
int sum = solve();
// for(int i = 0 ; i < m; i ++)
// cout<<colSwitch[i]<<' ';
// cout<<'\n'<<sum<<"\n\n";
if(sum > maxSum)
maxSum = sum;
}else{
colSwitch[row] = 1;
backtrack(row + 1);
colSwitch[row] = -1;
backtrack(row + 1);
}
}
void write(){
out << maxSum;
for(int i = 0 ; i < n ; i++)
delete[] matrix[i];
delete[] matrix;
delete[] colSwitch;
}
int main() {
read();
backtrack(0);
write();
return 0;
}