Pagini recente » Cod sursa (job #260765) | Cod sursa (job #1474656) | Cod sursa (job #1394686) | Cod sursa (job #374585) | Cod sursa (job #480571)
Cod sursa(job #480571)
#include <iostream>
#include <fstream>
#include <limits.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int matr[16][16], n, m, sum, maxim;
bool minMask[65536];
int getSum(int matr[16][16])
{
int s = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
s += matr[i][j];
return s;
}
template <class T>
void copyMatr(T m1[16][16], T m2[16][16], int n, int m)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
m1[i][j] = m2[i][j];
}
void calcSum(bool mask[], int k) {
int cop[16][16];
copyMatr<int>(cop, matr, 16, 16);
for (int j = 0; j < k; j++)
{
if (mask[j])
{
for (int i = 0; i < n; i++)
cop[i][j] *= -1;
for (int i = 0; i < n; i++)
{
int sLin = 0;
for (int k = 0; k < m; k++)
sLin += cop[i][k];
if (sLin < 0)
{
for (int l = 0; l < n; l++)
cop[i][l] *= -1;
}
sum = getSum(cop);
if (sum > maxim)
maxim = sum;
}
}
}
}
int next(bool mask[], int n) {
int i;
for (i = 0; (i < n) && mask[i]; ++i)
mask[i] = false;
if (i < n) {
mask[i] = true;
return 1;
}
return 0;
}
int main() {
maxim = INT_MIN;
for (int i = 0; i < 65536; i++)
minMask[i] = false;
f>>n>>m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
f>>matr[i][j];
bool mask[65536];
int i;
for (i = 0; i < m; ++i)
mask[i] = false;
// 2 ^ m posibilitati
calcSum(mask, m);
/* Print all the others */
while (next(mask, m))
calcSum(mask, m);
cout<<maxim<<endl;
g<<maxim<<endl;
return 0;
}