1391D - 505 - CodeForces Solution

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define r_all(x) x.rbegin(), x.rend()
#define sz(x) (ll) x.size()
#define g_max(x, y) x = max(x, y)
#define g_min(x, y) x = min(x, y)
#define rsz(a, n) a.resize(n)
#define ass(a, n) a.assign(n, 0)
#define YES() cout << "YES\n"
#define Yes() cout << "Yes\n"
#define NO() cout << "NO\n"
#define No() cout << "No\n"
#define endl "\n"
#define print(a)          \
    for (auto &x : a)     \
        cout << x << " "; \
    cout << endl
#define print_pair(a)
#define FOR(i, fr, to) for (long long i = fr; i <= to; i++)
#define RFOR(i, fr, to) for (long long i = fr; i >= to; i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define is insert
#define F first
#define S second

using namespace std;

using ll = long long;
using ld = long double;

using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using stkll = stack<ll>;
using qll = queue<ll>;
using dqll = deque<ll>;
using sll = set<ll>;
using msll = multiset<ll>;
using mll = map<ll, ll>;
using vsll = vector<sll>;
using sc = set<char>;
using pcll = pair<char, ll>;

ll dr[] = {0, 1, 0, -1}, dc[] = {-1, 0, 1, 0};
// ll dr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
// ll dc[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const ll INF = 1e18;
const double PI = 3.1415926535897;
ll MOD = 1e9 + 7;

struct MLong
{
    ll val;

    MLong() { val = 0; }

    MLong(const ll &v)
    {
        val = (-MOD <= v && v < MOD) ? v : v % MOD;
        if (val < 0)
            val += MOD;
    }

    friend ostream &operator<<(ostream &os, const MLong &a) { return os << a.val; }

    friend bool operator==(const MLong &a, const MLong &b) { return a.val == b.val; }

    friend bool operator!=(const MLong &a, const MLong &b) { return !(a == b); }

    friend bool operator<(const MLong &a, const MLong &b) { return a.val < b.val; }

    MLong operator-() const { return MLong(-val); }

    MLong &operator+=(const MLong &m)
    {
        if ((val += m.val) >= MOD)
            val -= MOD;
        return *this;
    }

    MLong &operator-=(const MLong &m)
    {
        if ((val -= m.val) < 0)
            val += MOD;
        return *this;
    }

    MLong &operator*=(const MLong &m)
    {
        val = (ll)val * m.val % MOD;
        return *this;
    }

    friend MLong ipow(MLong a, ll p)
    {
        MLong ans = 1;
        for (; p; p /= 2, a *= a)
            if (p & 1)
                ans *= a;
        return ans;
    }

    friend MLong inv(const MLong &a)
    {
        assert(a.val);
        return ipow(a, MOD - 2);
    }

    MLong &operator/=(const MLong &m) { return (*this) *= inv(m); }

    friend MLong operator+(MLong a, const MLong &b) { return a += b; }

    friend MLong operator-(MLong a, const MLong &b) { return a -= b; }

    friend MLong operator*(MLong a, const MLong &b) { return a *= b; }

    friend MLong operator/(MLong a, const MLong &b) { return a /= b; }

    operator int64_t() const { return val; }
};

template <class T>
vector<T> operator+(vector<T> a, vector<T> b)
{
    a.insert(a.end(), b.begin(), b.end());
    return a;
}

pll operator+(pll a, pll b)
{
    pll ans = {a.first + b.first, a.second + b.second};
    return ans;
}

template <class A, class B>
ostream &operator<<(ostream &os,
                    const pair<A, B> &p)
{
    os << p.first << " " << p.second;
    return os;
}

template <class A, class B>
istream &operator>>(istream &is, pair<A, B> &p)
{
    is >> p.first >> p.second;
    return is;
}

template <class T>
ostream &operator<<(ostream &os,
                    const vector<T> &vec)
{
    for (auto &x : vec)
    {
        os << x << " ";
    }

    return os;
}

template <class T>
istream &operator>>(istream &is, vector<T> &vec)
{
    for (auto &x : vec)
    {
        is >> x;
    }

    return is;
}

template <class T>
ostream &operator<<(ostream &os,
                    const set<T> &vec)
{
    for (auto &x : vec)
    {
        os << x << " ";
    }

    return os;
}

template <class A, class B>
ostream &operator<<(ostream &os,
                    const map<A, B> d)
{
    for (auto &x : d)
    {
        os << "(" << x.first << " " << x.second << ") ";
    }

    return os;
}

template <class A>
void read_arr(A a[], ll from, ll to)
{
    for (ll i = from; i <= to; i++)
    {
        cin >> a[i];
    }
}

template <class A>
void print_arr(A a[], ll from, ll to)
{
    for (ll i = from; i <= to; i++)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
}

template <class A>
void print_arr(A a[], ll n)
{
    print_arr(a, 0, n - 1);
}

template <class A>
void set_arr(A a[], A val, ll from, ll to)
{
    for (ll i = from; i <= to; i++)
    {
        a[i] = val;
    }
}

template <class A>
void set_arr(A a[], A val, ll n)
{
    set_arr(a, val, 0, n - 1);
}

// template <class T>
// vector<T> operator()(set<T> &st)
// {
//     vector<T> res;
//     for (auto &x : st)
//     {
//         res.is(x);
//     }
// }

const ll N = 2e5 + 10;

ll n, k, q, m;
ll a[N];
string s, s1, s2, s3;

void init()
{
}

vvll grid;

ll mem[2][2][2][2][2], vis[2][2][2][2][2];

ll dist(ll a, ll b, ll c, ll d, ll e)
{
    if (vis[a][b][c][d][e])
    {
        return mem[a][b][c][d][e];
    }

    vis[a][b][c][d][e] = 1;
    ll ans = 1e9;

    for (ll i = 0; i < 2; i++)
    {
        for (ll j = 0; j < 2; j++)
        {
            for (k = 0; k < 2; k++)
            {
                if (i ^ j == d && j ^ k == e)
                {
                    g_min(ans, (a ^ i) + (b ^ j) + (c ^ k));
                }
            }
        }
    }

    return mem[a][b][c][d][e] = ans;
}

ll get_ans()
{
    if (n > 3)
    {
        return -1;
    }

    if (n == 1)
    {
        return 0;
    }

    if (n == 2)
    {
        pll p;

        FOR(i, 1, m)
        {
            p.F += (i - grid[1][i] - grid[2][i] + 10) % 2;
            p.S += (i - grid[1][i] - grid[2][i] + 11) % 2;
        }

        return min(p.F, p.S);
    }

    ll ans = 1e9;
    for (ll i = 0; i < 2; i++)
    {
        for (ll j = 0; j < 2; j++)
        {
            ll cur = 0;
            FOR(col, 1, m)
            {
                cur += dist(grid[1][col], grid[2][col], grid[3][col],
                            i ^ (col & 1), j ^ (col & 1));
            }

            g_min(ans, cur);
        }
    }

    return ans;
}

void single(ll t_id = 0)
{
    cin >> n >> m;

    grid.assign(n + 5, vll(m + 5, 0));

    FOR(i, 1, n)
    {
        FOR(j, 1, m)
        {
            char c;
            cin >> c;
            grid[i][j] = c - '0';
        }
    }

    cout << get_ans() << "\n";
}

void multiple()
{
    ll t;
    cin >> t;

    for (ll i = 0; i < t; i++)
    {
        single(i);
    }
}

int main(int argc, char *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

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

    // freopen("./output.txt", "w", stdout);
    // freopen("./input.txt", "r", stdin);
    // multiple();
    single();

    // make clear && make out && ./out

    return 0;
}