Pagini recente » Cod sursa (job #729729) | Cod sursa (job #2507727) | Cod sursa (job #2946617) | Cod sursa (job #2269583) | Cod sursa (job #2640734)
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n,m;
int nr=0;
int M[18][18];
long long maxim;
bool usei[18], usej[18];
void bkt(int nrlin, int nrcol)
{
if(nrlin>n&&nrcol>m)
{
nr++;
/*fout<<"nr: "<< nr << '\n';
fout<< "usei: ";
for(int i=1;i<=n;i++)
fout<< usei[i]<< ' ';
fout<< '\n';
fout<< "usej: ";
for(int j=1;j<=m;j++)
fout<< usej[j]<< ' ';
fout<< '\n';
fout<< "M modificat:\n";*/
long long s=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(usei[i]^usej[j])
{
//fout<< -M[i][j] << ' ';
s-=M[i][j];
}
else
{
//fout<< M[i][j] << ' ';
s+=M[i][j];
}
}
// fout<< '\n';
}
if(nr==1)
maxim=s;
else if(s>maxim)
maxim=s;
/*fout<< "s: ";
fout<< s << '\n';
fout<< "\n\n";*/
}
else
{
if(nrlin<=n)
{
usei[nrlin]=1;
bkt(nrlin+1,nrcol);
usei[nrlin]=0;
bkt(nrlin+1,nrcol);
}
if(nrcol<=m)
{
usej[nrcol]=1;
bkt(nrlin,nrcol+1);
usej[nrcol]=0;
bkt(nrlin,nrcol+1);
}
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
fin>>M[i][j];
bkt(1,1);
fout<< maxim << '\n';
return 0;
}