Pagini recente » Istoria paginii runda/rar28 | Cod sursa (job #1470861) | Cod sursa (job #2353776) | Cod sursa (job #2921236) | Cod sursa (job #1972134)
#include<fstream>
using namespace std;
fstream fin("flip.in",ios::in),fout("flip.out",ios::out);
long a[17][17],S=0;
int ss[33],sp[33],n,m;
void read(int nl, int nc)
{
int i;
int j;
for(i=1;i<=nl;i++)
for(j=1;j<=nc;j++)
fin>>a[i][j];
}
long sum()
{
long s=0;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
s+=a[i][j];
return s;
}
void flip(int nr)
{
int i,j;
if(nr<=n)
for(j=1;j<=m;j++)
a[nr][j]*=(-1);
else
for(i=1;i<=n;i++)
a[i][nr-n]*=(-1);
}
int sol_submult(int k)
{
return 1;
}
int valid_submult(int k)
{
if(k==1)
return 1;
if(ss[k-1]<ss[k])
return 1;
return 0;
}
int sol_permut(int nr, int k)
{
return (nr==k ? 1:0);
}
int valid_permut(int k)
{
int i;
for(i=1;i<=k-1;i++)
if(sp[k]==sp[i])
return 0;
return 1;
}
void backtrack_permut(int s[33],int nr, int k)
{
int i;
long sm=0;
for(i=1;i<=nr;i++)
{
sp[k]=s[i];
if(valid_permut(k))
{
if(sol_permut(nr,k))
{
for(int j=1;j<=k;j++)
{
flip(sp[j]);
sm=sum();
if(sm>S)
S=sm;
}
}
backtrack_permut(s,nr,k+1);
}
}
}
void backtrack_submult(int k)
{
int i,j;
for(i=1;i<=n+m;i++)
{
ss[k]=i;
if(valid_submult(k))
{
if(sol_submult(k))
backtrack_permut(ss,k,1);
backtrack_submult(k+1);
}
}
}
int main()
{
fin>>n>>m;
read(n,m);
S=sum();
backtrack_submult(1);
fout<<S;
fin.close();
fout.close();
return 0;
}