Pagini recente » Cod sursa (job #626778) | Cod sursa (job #558109) | Cod sursa (job #64475) | Cod sursa (job #2929723) | Cod sursa (job #3278362)
#include <bits/stdc++.h>
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
int n,m,l[20],c[20],st[20],sc[20],b[20][20],a[20][20],smax,x;
void verif()//O(n*m)
{
int suma=0;
// for(int i=1;i<=n;i++)
// for(int j=1;j<=m;j++)
// b[i][j]=a[i][j];
// for(int j=1;j<=m;j++)
// sc[j]=c[j];
// for(int i=1; i<=n; i++)
// {
// if(!st[i])
//// suma+=l[i];
//// else
//// suma+=(l[i]*(-1));
// if(st[i])
// {
// for(int j=1; j<=m; j++)
// {
// sc[j]+=2*(-1*a[i][j]);
// b[i][j]=-b[i][j];
// }
//
// }
// }
for(int j=1; j<=m; j++)
{
if(sc[j]<0)
suma+=abs(sc[j]);
else
suma+=sc[j];
}
if(suma>smax)
smax=suma;
}
void back(int k)//O(2^n*verif)
{
if(k>n)
verif();
else
{
for(int i=0; i<=1; i++) ///0 nu fac nimic la 1 inm cu -1
{
st[k]=i;
if(i==1)
{
for(int j=1;j<=m;j++)
b[k][j]=-1*a[k][j],sc[j]+=(-2*a[k][j]);
}
back(k+1);
if(i==1)
for(int j=1;j<=m;j++)
b[k][j]=b[k][j]*(-1),sc[j]+=2*a[k][j];
}
}
}
int main()//O(back)
{
in>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
in>>a[i][j];
l[i]+=a[i][j];
c[j]+=a[i][j];
b[i][j]=a[i][j];
sc[j]=c[j];
}
smax=0;
back(2);
out<<smax;
return 0;
}