Pagini recente » Cod sursa (job #1572068) | Cod sursa (job #632445) | Cod sursa (job #336779) | Cod sursa (job #2260469) | Cod sursa (job #804795)
Cod sursa(job #804795)
#include <fstream>
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
const int N=17;
int n,m,result=-(1<<30),matrixval;
int a[N][N],sl[N],sc[N],soli[1<<N],sol[1<<N]; // suma linie si suma coloana de N
void read(){
in>>n>>m;
int i,j;
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
in>>a[i][j];
matrixval+=a[i][j];
}
}
}
int msb(int val){
int i=0;
for(;val;i++,val=val>>1);
return i-1;
}
int flip(int mb,int i){
int val=0;
for(int l=1;i;i>>=1,l++){
if(i&1){
val+=(4*a[l][mb]);
}
}
return val;
}
void solve(){
int sublin=1<<n;
int subcol=1<<m;
int i,j;
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
sl[i]+=a[i][j];
}
}
for(i=1;i<=m;++i){
for(j=1;j<=n;++j){
sc[i]+=a[j][i];
}
}
sol[0]=matrixval;
soli[0]=matrixval;
int mb;
for(j=1;j<subcol;++j){
mb=msb(j);
sol[j]=sol[j^(1<<mb)]-2*sc[mb+1];
if(sol[j]>result){
result=sol[j];
}
}
for(i=1;i<sublin;++i){
mb=msb(i);
sol[0]=soli[i^(1<<mb)]-2*sl[mb+1];
soli[i]=sol[0];
for(j=1;j<subcol;++j){
mb=msb(j);
sol[j]=sol[j^(1<<mb)]-2*sc[mb+1]+flip(mb+1,i);
if(sol[j]>result){
result=sol[j];
}
}
}
out<<result;
}
int main(){
read();
solve();
return 0;
}