Cod sursa(job #3138391)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 19 iunie 2023 13:20:59
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 16;
const int MAX_M = 16;

int n, m, ans;
int a[MAX_N + 1][MAX_M + 1], sol[MAX_N + 1], sumP[MAX_N + 1][MAX_M + 1];

void calculate()
{
    for(int i = 1; i <= n; i ++)
    {
        int coef = -sol[i - 1];
        if(!coef)
            coef = 1;
        for(int j = 1; j <= m; j ++)
            sumP[i][j] = sumP[i - 1][j] + coef * a[i][j];
    }

    int sum = 0;
    for(int j = 1; j <= m; j ++)
        sum += max(sumP[n][j], -sumP[n][j]);

    ans = max(ans, sum);
}

void bkt(int k)
{
    if(k == n)
    {
        calculate();
        return;
    }
    for(int i = 0; i <= 1; i ++)
    {
        sol[k] = i;
        bkt(k + 1);
    }
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

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

    cin >> n >> m;

    for(int i = 1 ; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> a[i][j];


    bkt(0);

    cout << ans;
    return 0;
}