Cod sursa(job #1753843)

Utilizator Burbon13Burbon13 Burbon13 Data 7 septembrie 2016 11:19:16
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>

using namespace std;

const int nmx = 17;

int n,m;
int mat[nmx][nmx];
int sum_max = -1;

void citire()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            scanf("%d", &mat[i][j]);
}

inline int max(const int &v1, const int &v2)
{
    return v1 > v2 ? v1 : v2;
}

void backtracking()
{
    for(int comb = 0; comb < (1 << n); ++comb)
    {
        int sum = 0;

        for(int j = 1; j <= m; ++j)
        {
            int sum_aux = 0;
            for(int i = 1; i <= n; ++i)
                if(comb & (1 << (i-1)))
                    sum_aux += mat[i][j];
                else
                    sum_aux -= mat[i][j];

            if(sum_aux >= 0)
                sum += sum_aux;
            else
                sum -= sum_aux;
        }

        sum_max = max(sum,sum_max);
    }
}

int main()
{
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);
    citire();
    backtracking();
    printf("%d\n", sum_max);
    return 0;
}