Cod sursa(job #2608767)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 1 mai 2020 18:39:51
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 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], sposl[5 + N], snegl[5 + N], sposc[5 + N], snegc[5 + N];

int main() {
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);
    int n, m, 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]);

            if(a[i][j] > 0) sposl[i] += a[i][j], sposc[j] += a[i][j];
            else snegl[i] -= a[i][j], snegc[j] -= a[i][j];
            sum += a[i][j];
        }
    }

    ans = sum;
    for(int mask = 0; mask < (1 << n); mask++) {
        int sum2 = sum;
        for(int j = 0; (1 << j) <= mask; j++) {
            if(mask & (1 << j)) {
                sum2 -= 2 * sposl[j];
                sum2 += 2 * snegl[j];
            }
        }

        for(int j = 1; j <= m; j++) {
            if(snegc[j] > sposc[j]) {
                sum2 -= 2 * sposc[j];
                sum2 += 2 * snegc[j];
            }
        }

        if(sum2 >= ans) {
            ans = sum2;
        }
    }

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