Pagini recente » Cod sursa (job #1018041) | Cod sursa (job #2884021) | Cod sursa (job #3122474) | Cod sursa (job #1515497) | Cod sursa (job #3036426)
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
vector<int> submultime;
int n, m, sol = INT_MIN;
int a[20][20];
void flip_linie(int lin)
{
for(int i = 1; i <= m; i++)
a[lin][i] *= -1;
}
void backtracking(int lin)
{
if(lin == n)
{
for(int i = 0; i < submultime.size(); i++)
flip_linie(submultime[i]);
int total = 0;
for(int j = 1; j <= m; j++)
{
int sumCol = 0;
for(int i = 1; i <= n; i++)
sumCol += a[i][j];
total += abs(sumCol);
}
sol = max(sol, total);
for(int i = 0; i < submultime.size(); i++)
flip_linie(submultime[i]);
return;
}
submultime.push_back(lin);
backtracking(lin+1);
submultime.pop_back();
backtracking(lin+1);
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
fin >> a[i][j];
backtracking(1);
fout << sol;
return 0;
}