Pagini recente » Cod sursa (job #1938525) | Cod sursa (job #2555849) | Cod sursa (job #982877) | Cod sursa (job #2891769) | Cod sursa (job #1662355)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
const long long minim=-17000000;
bool semn[18][18];
long long a[18][18],s;
long long suma_lin=17000000,suma_col=17000000;
int indice_lin,indice_col;
int n,m;
void citire()
{
int i,j;
fin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fin>>a[i][j];
}
void calculare_lin()
{
int i,j;
suma_lin=17000000;
long long suma=0;
for(i=1;i<=n;i++)
{
suma=0;
for(j=1;j<=m;j++)
suma+=a[i][j];
if(suma<suma_lin)
{
suma_lin=suma;
indice_lin=i;
}
}
}
void calculare_col()
{
int i,j;
suma_col=17000000;
long long suma=0;
for(j=1;j<=m;j++)
{
suma=0;
for(i=1;i<=n;i++)
suma+=a[i][j];
if(suma<suma_col)
{
suma_col=suma;
indice_col=j;
}
}
}
void schimbare_lin(int linie)
{
int i;
for(i=1;i<=m;i++)
a[linie][i]*=-1;
}
void schimbare_col(int coloana)
{
int i;
for(i=1;i<=n;i++)
a[i][coloana]*=-1;
}
void bkt()
{
bool ok=false;
while(!ok)
{
ok=true;
calculare_lin();
calculare_col();
if(suma_lin<suma_col)
{
if(suma_lin<0)
{schimbare_lin(indice_lin);
ok=false;
}
}
else
{
if(suma_col<0)
{
schimbare_col(indice_col);
ok=false;
}
}
}
}
void calculare()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
s+=a[i][j];
}
int main()
{
citire();
bkt();
calculare();
fout<<s;
return 0;
}