Cod sursa(job #2767305)

Utilizator Iulia25Hosu Iulia Iulia25 Data 5 august 2021 16:06:28
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("flip.in");
ofstream cout("flip.out");

int a[20][20];
bool flip[20];

int main()  {
    int n, m, ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    for (int i = 1; i < (1 << m); ++i)  { ///genereare submultimi coloane

        for (int s = i, j = 1; j <= m; s >>= 1, ++j) {
            if (s & 1)  {
                flip[j] = true; ///marchez daca fac filp sau nu la coloana j
            }
            else flip[j] = false;
        }

        int sum = 0; ///suma optima pentru submutimea de coloane la care am dat flip
        for (int l = 1; l <= n; ++l)    {
            int sum_linie = 0; ///suma de pe linia l

            for (int c = 1; c <= m; ++c)    {
                if (flip[c])
                    sum_linie += - a[l][c]; ///daca am dat flip la coloana c atunci scad a[l][c]
                else sum_linie += a[l][c]; ///altfel adun
            }

            if (sum_linie < 0)
                sum += - sum_linie; ///fac flip daca e cazul
            else sum += sum_linie;
        }

        if (sum > ans) ///retin suma maxima
            ans = sum;
    }
    cout << ans;
    return 0;
}