Pagini recente » Cod sursa (job #3314077) | Cod sursa (job #3329059) | Monitorul de evaluare | Cod sursa (job #163422) | Cod sursa (job #3340394)
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
const int Nmax = 20;
int n, m;
long long sol;
int mat[Nmax][Nmax];
bool is_fliped[Nmax];
void citire(){
fin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
fin >> mat[i][j];
}
}
}
void flip(){
for(int i = 1; i <= n; i++){
if(is_fliped[i]){
for(int j = 1; j <= m; j++){
mat[i][j] *= (-1);
}
}
}
}
void verificare_suma(){
long long sum, suma_coloana;
flip();
sum = 0;
for(int j = 1; j <= m; j++){
suma_coloana = 0;
for(int i = 1; i <= n; i++){
suma_coloana += mat[i][j];
}
if(suma_coloana < 0){
sum -= suma_coloana;
}
else{
sum += suma_coloana;
}
}
sol = max(sol, sum);
flip();
}
void backtracking(int poz){
if(poz == n + 1){
verificare_suma();
return;
}
for(int fliped = 0; fliped <= 1; fliped++){
is_fliped[poz] = fliped;
backtracking(poz + 1);
}
}
void afisare(){
fout << sol;
}
int main(){
citire();
sol = 0;
backtracking(1);
afisare();
return 0;
}