Pagini recente » Cod sursa (job #1906932) | Monitorul de evaluare | Cod sursa (job #1657151) | Cod sursa (job #2015981) | Cod sursa (job #2854201)
#include <fstream>
#include <set>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n, m, a[20][20], max_sum;
set<int, greater<int>> lin, col;
void flip(int k)
{
for (int i = 1; i <= m; ++i)
a[k][i] *= -1;
}
void flip2(int k)
{
for (int i = 1; i <= n; ++i)
a[i][k] *= -1;
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
fin >> a[i][j];
a[0][j] += a[i][j];
a[i][0] += a[i][j];
}
for (int i = 1; i <= n; ++i)
if (a[i][0] < 0)
lin.insert(i);
for (int i = 1; i <= m; ++i)
if (a[0][i] < 0)
col.insert(i);
while (!lin.empty() && !col.empty())
if (a[*lin.begin()][0] < a[0][*col.begin()])
{
flip(*lin.begin());
lin.erase(*lin.begin());
}
else
{
flip2(*col.begin());
col.erase(*col.begin());
}
if (!lin.empty())
{
flip(*lin.begin());
lin.erase(*lin.begin());
}
if (!col.empty())
{
flip2(*col.begin());
col.erase(*col.begin());
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
max_sum += a[i][j];
fout << max_sum;
fin.close();
fout.close();
return 0;
}