Pagini recente » Cod sursa (job #2914039) | Cod sursa (job #680159) | Cod sursa (job #79041) | Cod sursa (job #2340610) | Cod sursa (job #2908234)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("flip.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[n];
}
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 == n){
int m = solve();
if(m > maxSum)
maxSum = m;
}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;
}