Pagini recente » Cod sursa (job #1811416) | Cod sursa (job #2168572) | Cod sursa (job #1401451) | Cod sursa (job #2175036) | Cod sursa (job #597696)
Cod sursa(job #597696)
#include <fstream>
#include <cstring>
#define MAX1 16
using namespace std;
ifstream in;
ofstream out;
int A[MAX1][MAX1],B[MAX1][MAX1];
int sol[MAX1],v[MAX1];
int S,N,M;
inline void Cverif()
{
int s=0;
memset(v,0,sizeof(v));
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
B[i][j]=A[i][j];
for(int j=1;j<=N;++j)
if(sol[j]==1)
for(int i=0;i<M;++i)
B[i][j-1]*=-1;
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
v[i]+=B[i][j];
for(int i=0;i<M;++i)
if(v[i]>0) s+=v[i];
else s-=v[i];
if(s>S) S=s;
return;
}
inline void Lverif()
{
int s=0;
memset(v,0,sizeof(v));
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
B[i][j]=A[i][j];
for(int i=1;i<=M;++i)
if(sol[i]==1)
for(int j=0;j<N;++j)
B[i-1][j]*=-1;
for(int j=0;j<N;++j)
for(int i=0;i<M;++i)
v[j]+=B[i][j];
for(int j=0;j<N;++j)
if(v[j]>0) s+=v[j];
else s-=v[j];
if(s>S) S=s;
return;
}
inline void Cback(int k)
{
if(k>N) Cverif();
else
for(int i=0;i<2;++i)
{
sol[k]=i;
Cback(k+1);
}
}
inline void Lback(int k)
{
if(k>M) Lverif();
else
for(int i=0;i<2;++i)
{
sol[k]=i;
Lback(k+1);
}
}
int main()
{
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) Cback(1);
else Lback(1);
out.open("flip.out");
out<<S<<'\n';
out.close();
return 0;
}