Cod sursa(job #635181)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
struct tab
{
int t[256];
short m;
short n;
};
int put2 (short a)
{
short n;
for (n=1;a;a--)
n=n*2;
return n;
}
char val (short a)
{
return a+'0';
}
char* bin (int n, int p2)
{
char s1[16],r1[16];
char *s,*r;
s=s1;
r=r1;
strcpy(s,"");
short i,l;
for (i=0;n;n=n/2,i++)
s[i]=val(n%2);
s[i]='\0';
for (;i<p2;i++)
strcat(s,"0");
l=i;
s[l]='\0';
strcpy(r,s);
for (i=0;i!=l;i++)
r[i]=s[l-i-1];
r[l]='\0';
return r;
}
tab flipl (tab a, short i)
{
short j;
for (j=0;j<a.m;j++)
a.t[i*a.m+j]=-a.t[i*a.m+j];
return a;
}
tab flipc (tab a, short i)
{
short j;
for (j=0;j<a.n;j++)
a.t[j*a.m+i]=-a.t[j*a.m+i];
return a;
}
int suma (tab a)
{
int s=0;
short i;
for (i=0;i<a.m*a.n;i++)
s=s+a.t[i];
return s;
}
int sumac (tab a, char* s)
{
short j;
int S,max=0;
tab b;
for (j=0;j<a.n;j++)
if (s[j]=='1')
a=flipl(a,j);
max=suma(a);
for (j=0;j<a.m;j++)
{
b=flipc(a,j);
S=suma(b);
if (S>max)
max=S;
}
return max;
}
int comb (tab a)
{
short i,p;
int max=0,S;
p=put2(a.n);
for (i=0;i<p;i++)
{
S=sumac(a,bin(i,a.n));
if (S>max)
max=S;
}
return max;
}
int main ()
{
fstream f("flip.in", ios::in);
fstream g("flip.out", ios::out);
short i,j;
tab a;
f>>a.n>>a.m;
for (i=0;i<a.n;i++)
for (j=0;j<a.m;j++)
f>>a.t[i*a.m+j];
g<<comb(a);
g.close ();
}