Pagini recente » Cod sursa (job #488504) | Cod sursa (job #2078741)
#include <fstream>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int i,j,q1[17],q2[17],s,Max,v[17][17],n,m,s1[17],s2[17];
void back(int x,int y)
{
int i,j,k;
for(j=y+1;j<=m;j++)
{
q1[x]*=(-1);
q2[j]*=(-1);
int t=s;
s-=(s1[x]+s2[j]-v[x][j]);
for(k=1;k<=n;k++)
s+=v[k][j]*q1[k]*q2[j];
for(k=1;k<=m;k++)
s+=v[x][k]*q1[x]*q2[k];
s-=v[x][j]*q1[x]*q2[j];
Max=max(Max,s);
if(x<=n&&y<m)
back(x,j+1);
else
if(x<n&&y==m)
back(x+1,1);
s=t;
q2[j]*=(-1);
q1[x]*=(-1);
}
for(i=x+1;i<=n;i++)
for(j=1;j<=m;j++)
{
q1[i]*=(-1);
q2[j]*=(-1);
int t=s;
s-=(s1[i]+s2[j]-v[i][j]);
for(k=1;k<=n;k++)
s+=v[k][j]*q1[k]*q2[j];
for(k=1;k<=m;k++)
s+=v[i][k]*q1[i]*q2[k];
s-=v[i][j]*q1[i]*q2[j];
Max=max(Max,s);
if(x<=n&&y<m)
back(i,j+1);
else
if(x<n&&y==m)
back(i+1,1);
s=t;
q2[j]*=(-1);
q1[i]*=(-1);
}
}
int main()
{
f>>n>>m;
for(i=1;i<=n;i++)
{
q1[i]=1;
for(j=1;j<=m;j++)
{
f>>v[i][j];
s+=v[i][j];
s1[i]+=v[i][j];
s2[j]+=v[i][j];
}
}
for(j=1;j<=m;j++)
q2[j]=1;
Max=s;
back(1,1);
g<<Max;
return 0;
}