Pagini recente » Cod sursa (job #896767) | Cod sursa (job #1063565) | Cod sursa (job #1769553) | Cod sursa (job #1987279) | Cod sursa (job #1870276)
#include <fstream>
#include <vector>
std::ifstream fin("flip.in");
std::ofstream fout("flip.out");
std::vector<std::vector<int>> table;
std::vector<int> line;
#define MAX 17
long long outputsum;
int n, m;
int linesum;
int columnsum;
int i, j;
void backTrack(std::vector<std::vector<int>> table, long long sum, bool which, int i, int j)
{
if (sum>outputsum)
{
outputsum = sum;
if (which == 0)
{
for (auto j = 0; j < m; j++)
{
table[i][j] = -table[i][j];
}
}
else
{
for (auto j = 0; j < n; j++)
{
table[j][i] = -table[j][i];
}
}
}
else
{
if (sum<outputsum)
{
return;
}
}
for (auto i = 0; i < n; i++)
{
linesum = 0;
for (auto j = 0; j < m; j++)
{
linesum += table[i][j];
}
if (-linesum > linesum)
{
backTrack(table, sum + (-linesum) - linesum, 0, i, j);
}
}
for (auto i = 0; i < m; i++)
{
columnsum = 0;
for (auto j = 0; j < n; j++)
{
columnsum += table[j][i];
}
if (-columnsum > columnsum)
{
backTrack(table, sum + (-columnsum) - columnsum, 1, i, j);
}
}
}
int main(void)
{
long long sum = 0;
fin >> n >> m;
for (auto i = 0; i < n; i++)
{
line.clear();
for (auto j = 0; j < m; j++)
{
int x;
fin >> x;
line.push_back(x);
sum += x;
}
table.push_back(line);
}
outputsum = sum;
backTrack(table, sum, 0, 0, 0);
fout << outputsum;
}