Pagini recente » Cod sursa (job #1101707) | Cod sursa (job #914106) | Cod sursa (job #549655) | Cod sursa (job #439765) | Cod sursa (job #2278050)
#include <fstream>
#include <algorithm>
#define MAX 17
#define MIN -1000000000
using namespace std;
int a[MAX][MAX], sumeC[MAX], linii[MAX], Max = MIN;
void backtracking(int n, int m, int k)
{
if(k <= n)
{
linii[k] = 0;
backtracking(n, m, k + 1);
linii[k] = 1;
backtracking(n, m, k + 1);
}
else
{
int i, j;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
if(linii[i] == 1)sumeC[j] = sumeC[j] - 2 * a[i][j];
//sort(sume2C + 1, sume2C + 1 + m);
int suma = 0;
for(j = 1; j <= m; j++)
if(sumeC[j] < 0)suma += -sumeC[j];
else suma += sumeC[j];
if(suma > Max)Max = suma;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
if(linii[i] == 1)sumeC[j] = sumeC[j] + 2 * a[i][j];
}
}
int main()
{
int n, m, i, j;
ifstream fin("flip.in");
ofstream fout("flip.out");
fin >> n >> m;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
{
fin >> a[i][j];
sumeC[j] += a[i][j];
}
if(n > m)
{
swap(n, m);
}
backtracking(n, m, 1);
fout << Max;
fin.close();
fout.close();
return 0;
}