Pagini recente » Cod sursa (job #1471109) | Cod sursa (job #2777430)
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int mat[18][18], n, m, sum, ans, pr[18][18], S;
long long use;
void solve()
{
long long UPB = 1 << (n + m + 1);
for (use = 1; use < UPB; use++)
{
sum = S;
for (int i = 0; (1 << i) <= use; i++)
if (use & (1 << i))
{
int j = i + 1;
/*{fout << i + 1 << " ";
cout << i + 1 << " ";
}*/
if (j <= n)
for (int k = 1; k <= m; k++)
{
sum -= pr[j][k];
pr[j][k] *= -1;
sum += pr[j][k];
}
else
for (int k = 1; k <= n; k++)
{
sum -= pr[k][j - n];
pr[k][j - n] *= -1;
sum += pr[k][j - n];
}
}
ans = max(ans, sum);
memcpy(pr, mat, sizeof(mat));
//fout << "\n";
//cout << "\n";
}
}
int main()
{
int i, j;
fin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
fin >> mat[i][j];
S += mat[i][j];
pr[i][j] = mat[i][j];
}
ans = S;
//backt(1);
solve();
//de implementat generarea submultimilor folosind un nr si
// operatii pe biti
fout << ans;
}