Cod sursa(job #2685867)

Utilizator andrei_ciobanuciobanu andrei andrei_ciobanu Data 17 decembrie 2020 21:02:08
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#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];
int n, m;
int max_sum;


void verify(){
    int sum=0, s;
    int i, j;
    for (j=0; j<m; j++){
        s=0;
        for (i=0; i<n; i++){
            s+=a[i][j]*combs[i];
        }
        if (s>0) sum+=s;
        else sum-=s;
    }
    if (sum>max_sum) max_sum=sum;
}

void bkt(int line){
    if (line==n){
        verify();
        return;
    }
    combs[line]=-1;
    bkt(line+1);
    combs[line]=1;
    bkt(line+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];
            max_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;
    }
    bkt(0);

    FILE *fout=fopen("flip.out", "w");
    fprintf(fout, "%d", max_sum);
    return 0;
}