Cod sursa(job #1746872)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 24 august 2016 01:58:10
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
using namespace std;
const int DIM = 16;
int a[DIM + 5][DIM + 5], aux[DIM + 5][DIM + 5];
void copy(int n, int m){
    int i, j;
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= m; j ++)
            aux[i][j] = a[i][j];
}
int solve(int n, int m, int s){
    int i, j;
    long long sum;
    for (j = 1; j <= m; j ++){
        sum = s;
        for (i = 1; i <= n; i ++)
            sum -=  2 * aux[i][j];
        if (sum > s){
            s = sum;
            for (i = 1; i <= n; i ++)
                aux[i][j] = -aux[i][j];
        }
    }
    return s;
}
int main(){
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);
    int n, m, i, j, k, ns, s = 0, sum, max = -256000000;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= m; j ++){
            scanf("%d", &a[i][j]);
            s += a[i][j];
        }
    ns = (1 << n) - 1;
    for (i = 1; i <= ns; i ++){
        copy(n, m);
        sum = s;
        for (j = 0; j < n; j ++)
            if ((1 << j) & i)
                for (k = 1; k <= m; k ++){
                    sum -= 2 * aux[j + 1][k];
                    aux[j + 1][k] = -aux[j + 1][k];
                }
        sum = solve(n, m, sum);
        max = max > sum ? max:sum;
    }
    printf("%d\n", max);
    return 0;
}