Cod sursa(job #598782)

Utilizator DanytzuBran Daniel Danytzu Data 27 iunie 2011 01:12:36
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#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 Cverific()
{
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<'\n';
out.close();
 
return 0;
}