Cod sursa(job #2242309)

Utilizator FrequeAlex Iordachescu Freque Data 18 septembrie 2018 12:06:45
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>
#define Hack cin.sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <pii> vii;
typedef vector <ll> vl;
typedef vector <pll> vll;
typedef queue <int> qi;
typedef queue <pii> qii;
typedef queue <ll> ql;
typedef queue <pll> qll;

const int INF = 0x3f3f3f3f;
const int MOD = 666013;
const int NMAX = 20 + 5;

ifstream fin("submultimi.in");
ofstream fout("submultimi.out");

int n, m, ans = -INF;
int semn_linie[NMAX];
int a[NMAX][NMAX];

void col()
{
    int sum = 0;
    for (int j = 1; j <= m; ++j)
    {
        int curr = 0;
        for (int i = 1; i <= n; ++i)
            curr += a[i][j] * semn_linie[i];
        sum += abs(curr);
    }

    ans = max(ans, sum);
}

void backtr(int poz)
{
    if (poz == n)
    {
        col();
        return;
    }

    backtr(poz + 1);

    semn_linie[poz] = -1;
    backtr(poz + 1);
    semn_linie[poz] = 1;
}

int main()
{
    Hack;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        semn_linie[i] = 1;
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    }

    backtr(1);
    cout << ans;

    return 0;
}