Pagini recente » Cod sursa (job #1191342) | Cod sursa (job #517446) | Cod sursa (job #2812905) | Cod sursa (job #637509) | Cod sursa (job #849715)
Cod sursa(job #849715)
#include<fstream>
#include<vector>
#include<iostream>
#include<set>
using namespace std;
ofstream fout("flip.out");
long flip_and_sum(vector<vector<long> > ctable,vector<bool>& bit_map,int n,int m)
{
int i ,j;
long s = 0;
for(i=0;i<n;++i)
if(bit_map[i])
for(j=0;j<m;++j)
ctable[i][j]*=-1;
for(j=n;j<m+n;++j)
if(bit_map[j])
for(i=0;i<n;i++)
if(!bit_map[i])
ctable[i][j-n]*=-1;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
s += ctable[i][j];
return s;
}
void back_gen(vector<bool>& bit_map,int k,int limit,set<vector<bool> >& results)
{
if(k == limit+1)
{
results.insert(bit_map);
}
else
{
bit_map[k] = 0;
back_gen(bit_map,k+1,limit,results);
bit_map[k] = 1;
back_gen(bit_map,k+1,limit,results);
}
}
int main()
{
int n,m,i,j,k;
long max_sum=0,temp;
ifstream fin("flip.in");
fin>>n>>m;
vector<vector<long> >table(n,vector<long>(m,0)),ctable;
vector<bool> bit_map (n+m);
set<vector<bool> > configs;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
fin>>table[i][j];
fin.close();
back_gen(bit_map,0,n+m,configs);
for(set<vector<bool> >::iterator k=configs.begin();k!=configs.end();++k )
{
bit_map = *k;
temp = flip_and_sum(table,bit_map,n,m);
if(temp>max_sum)
max_sum = temp;
}
fout<<max_sum;
return 0;
}