Pagini recente » Cod sursa (job #1218509) | Cod sursa (job #1454435) | Cod sursa (job #2987577) | Cod sursa (job #2768906) | Cod sursa (job #3136668)
#include <bits/stdc++.h>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int n, m, A[20][20], sol[20], fr[20], maxi = INT_MIN, v[20], sumilin[20], sumicol[20 ];
void verif1(int k)
{
int sumi = 0;
for(int i = 1; i <= k; i ++)
sumi += sumilin[sol[i]] * (-1);
if(sumi > maxi)
{
for(int i = 1; i <= k; i ++)v[i] = sol[i];
v[0] = k; maxi = sumi;
}
}
void comb1(int K)
{
if(K <= n)
{
for(int i = sol[K - 1] + 1; i <= n; i ++)
if(!fr[i]){
fr[i] = 1;
sol[K] = i;
verif1(K);
comb1(K + 1);
fr[i] = 0;
}
}
}
void verif2(int k)
{
int sumi = 0;
for(int i = 1; i <= k; i ++)
sumi += sumicol[sol[i]] *(-1);
if(sumi > maxi)
{
for(int i = 1; i <= k; i ++)v[i] = sol[i];
v[0] = k; maxi = sumi;
}
}
void comb2(int K)
{
if(K <= m)
{
for(int i = sol[K - 1] + 1; i <= m; i ++)
if(!fr[i]){
fr[i] = 1;
sol[K] = i;
verif2(K);
comb2(K + 1);
fr[i] = 0;
}
}
}
int main()
{
f >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
f >> A[i][j];
sumicol[j] += A[i][j];
sumilin[i] += A[i][j];
}
comb1(1);
for(int i = 1; i <= v[0]; i ++)
{
sumilin[v[i]] *= (-1);
for(int j = 1; j <= m; j ++)
{
A[v[i]][j] *= (-1);
sumicol[j] += 2 * A[v[i]][j];
}
}
maxi = INT_MIN; v[0] = 0;
comb2(1);
for(int i = 1; i <= v[0]; i ++)
sumicol[v[i]] *= (-1);
int sumi = 0;
for(int i = 1; i <= m; i ++)
sumi += sumicol[i];
g << sumi;
return 0;
}