Cod sursa(job #2856235)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 23 februarie 2022 16:36:18
Problema Jocul Flip Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("flip.in");
ofstream g("flip.out");

int n,m;
int mat[18][18];
bool lin_flip[18],col_flip[18];
int suminit,summax;

void read() {
    f >> n >> m;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            f >> mat[i][j];
            suminit += mat[i][j];
            mat[n+1][j] += mat[i][j];
            mat[i][m+1] += mat[i][j];
        }
    }
}


void line(int lin) {
    mat[lin][m+1] = -mat[lin][m+1];
    for (int j=1;j<=m;j++) {
        mat[lin][j] = -mat[lin][j];
        mat[n+1][j] += 2*mat[lin][j];
    }
}

void column(int col) {
    mat[n+1][col] = -mat[n+1][col];
    for (int i=1;i<=n;i++) {
        mat[i][col] = -mat[i][col];
        mat[i][m+1] += 2*mat[i][col];
    }
}

void bkt(int sum) {
    summax = max(summax,sum);
    for (int i=1;i<=n;i++) {
        if (mat[i][m+1]<0 && !lin_flip[i]) {
            line(i);
            lin_flip[i]=1;
            bkt(sum+2*mat[i][m+1]);
            line(i);
            lin_flip[i]=0;
        }
    }
    for (int j=1;j<=m;j++) {
        if (mat[n+1][j]<0 && !col_flip[j]) {
            column(j);
            col_flip[j]=1;
            bkt(sum+2*mat[n+1][j]);
            column(j);
            col_flip[j]=0;
        }
    }
}

int main()
{
    read();
    bkt(suminit);
    g << summax;
    return 0;
}