Pagini recente » Cod sursa (job #2440592) | Cod sursa (job #1507094) | Cod sursa (job #1265160) | Cod sursa (job #620526) | Cod sursa (job #597221)
Cod sursa(job #597221)
#include <fstream>
#include <cstring>
#define MAX1 16
using namespace std;
ifstream in;
ofstream out;
int A[MAX1][MAX1];
int sol[MAX1],v[MAX1];
int S,N,M;
inline void verif(int n)
{
int s=0;
for(int i=1;i<=n;++i)
if(sol[i]==0) s+=v[i-1];
else s+=-v[i-1];
if(s>S) S=s;
return;
}
inline void Cback(int k)
{
if(k>N) verif(N);
else
for(int i=0;i<2;++i)
{
sol[k]=i;
Cback(k+1);
}
}
inline void Lback(int k)
{
if(k>M) verif(M);
else
for(int i=0;i<2;++i)
{
sol[k]=i;
Lback(k+1);
}
}
int main()
{
memset(v,0,sizeof(v));
memset(A,0,sizeof(A));
memset(sol,0,sizeof(sol));
S=0;
in.open("flip.in");
in>>M>>N;
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
in>>A[i][j];
in.close();
if(M>N)
{
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
v[i]+=A[i][j];
for(int i=0;i<M;++i)
if(v[i]<0)
{
v[i]*=-1;
for(int j=0;j<N;++j)
A[i][j]*=-1;
}
memset(v,0,sizeof(v));
for(int j=0;j<N;++j)
for(int i=0;i<M;++i)
v[j]+=A[i][j];
Cback(1);
}
else
{
for(int j=0;j<N;++j)
for(int i=0;i<M;++i)
v[j]+=A[i][j];
for(int j=0;j<N;++j)
if(v[j]<0)
{
v[j]*=-1;
for(int i=0;i<M;++i)
A[i][j]*=-1;
}
memset(v,0,sizeof(v));
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
v[i]+=A[i][j];
Lback(1);
}
out.open("flip.out");
out<<S<<'\n';
out.close();
return 0;
}