Cod sursa(job #2431160)

Utilizator aviciiTim Bergling avicii Data 18 iunie 2019 12:57:35
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 16;
int n, m, mt[N][N];
int sum[N];

void read()
{
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
                for (int j = 0; j < m; j++)
                {
                        cin >> mt[i][j];
                        sum[i] += mt[i][j];
                }
        }
}

int solve()
{
        int best = 0;
        for (int mask = 0; mask < (1 << m); mask++)
        {
                for (int bit = 0; (1 << bit) <= mask; bit++)
                {
                        if (mask & (1 << bit))
                        {
                                for (int i = 0; i < n; i++)
                                {
                                        /// mt[i][bit] -> -mt[i][bit]
                                        sum[i] -= 2 * mt[i][bit];
                                }
                        }
                }
                int cur = 0;
                for (int i = 0; i < n; i++)
                {
                        cur += abs(sum[i]);
                }
                best = max(best, cur);
                for (int bit = 0; (1 << bit) <= mask; bit++)
                {
                        if (mask & (1 << bit))
                        {
                                for (int i = 0; i < n; i++)
                                {
                                        sum[i] += 2 * mt[i][bit];
                                }
                        }
                }
        }
        return best;
}

int main()
{
        freopen ("flip.in", "r", stdin);
        freopen ("flip.out", "w", stdout);

        read();

        int res = solve();
        cout << res << "\n";

}