Pagini recente » Cod sursa (job #1252665) | Cod sursa (job #1060252) | Cod sursa (job #1495274) | Cod sursa (job #71383) | Cod sursa (job #3319416)
#include <bits/stdc++.h>
using namespace std;
/*
F F F
1 1 -1 1 1 -> 1
1 1 -1 1 1 -> 1
-1 -1 30 -1 -1 -> -30 F
1 1 -1 1 1 -> 1
1 1 -1 1 1 -> 1
-----
34
*/
/*
2^nr_col <= 2^16 = 65536
*/
/* Plan de atac:
Luam totate variantele de flip pe coloane
Pentru o varianta de flip pe coloane determinam unde dam flip pe linii
Dintre toate astea luam maximul
*/
const int NMAX=20;
int N, M;
int mat[NMAX][NMAX];
int flip[NMAX];
int maxx=0;
void bkt(int k)
{
if(k==M+1)
{
int suma_totala=0;
for(int i=1;i<=N;++i)
{
int sum=0;
for(int j=1;j<=M;++j)
{
if(flip[j]==1)
sum=sum-mat[i][j];
else
sum=sum+mat[i][j];
}
if(sum>0)
suma_totala+=sum;
else
suma_totala-=sum;
}
if(maxx<suma_totala)
maxx=suma_totala;
}
else
{
for(flip[k]=0;flip[k]<2;++flip[k])
bkt(k+1);
}
}
int main()
{
ifstream cin("flip.in");
ofstream cout("flip.out");
cin>>N>>M;
for(int i=1;i<=N;++i)
for(int j=1;j<=M;++j)
cin>>mat[i][j];
/*
for(flip[1]=0;flip[1]<2;++flip[1])
for(flip[2]=0;flip[2]<2;++flip[2])
for(flip[3]=0;flip[3]<2;++flip[3])
...
{
// Pas 2
}
*/
bkt(1);
cout<<maxx<<'\n';
return 0;
}