Cod sursa(job #2608777)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 1 mai 2020 18:50:18
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>

using namespace std;

const int INF = 2e9;
const int N = 16;

int a[5 + N][5 + N];
long long s[5 + N];

int main() {
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);
    int n, m;
    long long sum, ans;
    scanf("%d%d", &n, &m);

    sum = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            sum += 1LL * a[i][j];
        }
    }

    ans = sum;
    for(int mask = 0; mask < (1 << n); mask++) {
        int sum2 = sum;
        for(int i = 0; (1 << i) <= mask; i++) {
            if(mask & (1 << i)) {
                for(int j = 1; j <= m; j++) {
                    sum -= a[i][j];
                }
            }
        }

        for(int j = 1; j <= m; j++) s[j] = 0;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if((1 << i) & mask)
                    s[j] -= 1LL * a[i][j];
                else s[j] += 1LL * a[i][j];
            }
        }

        sum = 0;
        for(int j = 1; j <= m; j++)
            sum += 1LL * (s[j] < 0 ? -s[j] : s[j]);

        if(sum >= ans) ans = sum;
    }

    printf("%lld\n", ans);
    return 0;
}