Pagini recente » Cod sursa (job #423701) | tema | Cod sursa (job #501654) | Cod sursa (job #413231) | Cod sursa (job #326143)
Cod sursa(job #326143)
#include <iostream>
#include <fstream>
using namespace std;
#define max(a , b) ((a > b) ? a : b)
int main(){
ifstream in;
ofstream out;
long int N, M, val, sol, MAXsol;
in.open("flip.in");
in >> N >> M;
long int A[N][M], col[M];
for (int i=0;i<M;i++) col [i] = 0;
for (int i=0;i<N;i++)
for (int j=0;j<M;j++){
in >> val;
A[i][j] = val;
col[j] += val;
}
in.close();
sol = 0; MAXsol = 0;
int p = 1, bck[N+1]; //Backtracking by N, no huge difference for M
for (int i=1; i<= N; i++) bck[i] = 0;
while (p != 0)
{
if (p > N)
{
//Test solution here
sol = 0;
for (int i=0; i< M; i++)
sol += max(col[i], -col[i]);
MAXsol = max(sol, MAXsol);
p--;
bck[p]++;
}
else
if (bck[p] == 2)
{
bck[p] = 0;
p--;
bck[p]++;
for (int j=0;j<M;j++)
{
col[j] -= 4*(bck[p]%2-0.5)*A[p-1][j];
}
}
else
p++;
}
out.open("flip.out");
out << MAXsol;
out.close();
return 0;
}