Cod sursa(job #2685864)

Utilizator andrei_ciobanuciobanu andrei andrei_ciobanu Data 17 decembrie 2020 20:53:01
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 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+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;
}