Pagini recente » Cod sursa (job #235791) | Cod sursa (job #721843) | Autentificare | Cod sursa (job #3171856) | Cod sursa (job #2685864)
#include <cstdio>
using namespace std;
#define MAXN 16
#define MAXM 16
int a[MAXN][MAXM];
int line_sum[MAXN+1], column_sum[MAXM+1];
int combs[MAXN+MAXM];
int n, m;
int total_sum, max_sum;
void verify(int pos){
int sum=total_sum;
int i;
for (i=1; i<=pos; i++){
//printf("%d ", combs[i]);
if (combs[i]<=n){
sum-=2*line_sum[combs[i]];
}else{
sum-=2*column_sum[combs[i]-n];
}
}
//printf("\n");
if (sum>max_sum) max_sum=sum;
}
void bkt(int pos){
if (pos>1) verify(pos-1);
if (pos==n+m+1) return;
if (pos<=n+m){
for (int i=combs[pos-1]+1; i<=n+m; i++){
combs[pos]=i;
bkt(pos+1);
}
}
}
int main()
{
FILE *fin=fopen("flip.in", "r");
fscanf(fin, "%d%d", &n, &m);
int i, j;
for (i=0; i<n; i++){
int s=0;
for (j=0; j<m; j++){
fscanf(fin, "%d", &a[i][j]);
s+=a[i][j];
total_sum+=a[i][j];
}
line_sum[i+1]=s;
}
for (j=0; j<m; j++){
int s=0;
for (i=0; i<n; i++) s+=a[i][j];
column_sum[j+1]=s;
}
max_sum=total_sum;
bkt(1);
FILE *fout=fopen("flip.out", "w");
fprintf(fout, "%d", max_sum);
return 0;
}