Cod sursa(job #546047)
#include<fstream>
#include<iostream>
using namespace std;
fstream f("filip.in",ios::in),
g("filip.out",ios::out);
int s[16],i,j,m,n,a[16][16],v,max1,x[100],k,b[17],smax;
void init (int k)
{
x[k]=-1;
}
int succ( int k)
{
if(k<=m&&x[k]<1)
{
x[k]++;
return 1;
}
return 0;
}
int valid( int k)
{
return 1;
}
int sol( int k)
{
if(k==m)
return 1;
return 0;
}
void tipar(int k)
{
int i,j,s,sl;
s=0;
for(i=1;i<=n;i++)
{
sl=b[i];
for(j=1;j<=m;j++)
if(x[j]==1)
sl=sl+2*(-1)*a[i][j];
if(sl<-sl)
s=s-sl;
else
s=s+sl;
}
if(s>smax)
smax=s;
}
void back()
{
int i, k;
k=1;
init(k);
while(k>0)
{
i=0;
while(i==0 && succ(k))
if(valid(k))
i=1;
if(i==1)
if(sol(k))
tipar(k);
else
{
k++;
init(k);
}
else
k--;
}
}
int main()
{
f>>n>>m;
for(i=1;i<=n;i++)
{
b[i]=0;
for(j=1;j<=m;j++)
{
f>>a[i][j];
b[i]=a[i][j]+b[i];
}
}
smax=0;
back();
g<<smax;
}