Language: C++

#include <bits/stdc++.h>
using namespace std;

using i64 = int64_t;

#define rep(i, x, y) for (i64 i = i64(x), i##_max_for_repmacro = i64(y); i < i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf = 1.01e9;
const i64 inf64 = 4.01e18;
const double eps = 1e-9;

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

template <typename T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T, size_t size> void fill(T (&ary)[size], const T& val){
    fill_n((T*)ary, size, val);
}

void solve() {
    //const i64 mod = 1'000'000'007;

    i64 H,W;
    cin >> H >> W;

    vector<string> A(H);
    rep(i,0,H) cin >> A[i];

    vector<vector<i64>> sum(H,vector<i64>(W));
    rep(i,0,H){
        rep(j,0,W){
            if(A[i][j]=='#') ++sum[i][j];
        }
    }
    rep(i,0,H){
        rep(j,1,W){
            sum[i][j]+=sum[i][j-1];
        }
    }
    rep(i,1,H){
        rep(j,0,W){
            sum[i][j]+=sum[i-1][j];
        }
    }

    auto count=[&](i64 t,i64 b,i64 l,i64 r){
        i64 res=sum[b][r];
        if(t>0) res-=sum[t-1][r];
        if(l>0) res-=sum[b][l-1];
        if(t>0 and l>0) res+=sum[t-1][l-1];
        return res;
    };

    using tup=tuple<i64,i64,i64,i64>;
    unordered_map<tup,i64> memo;
    function<i64(i64,i64,i64,i64)> rec=[&](i64 t,i64 b,i64 l,i64 r){
        auto s=make_tuple(t,b,l,r);
        if(memo.find(s)!=memo.end()) return memo[s];
        i64 v=(b-t+1)*(r-l+1);
        if(count(t,b,l,r)==v or count(t,b,l,r)==0) return i64(0);

        i64 res=inf64;
        if(t<b){
            i64 lb=t,ub=b;
            while(ub-lb>1){
                i64 mid=(lb+ub)/2;
                if(rec(t,mid,l,r)<=rec(mid+1,b,l,r)) lb=mid;
                else ub=mid;
            }
            chmin(res,max(rec(t,lb,l,r),rec(lb+1,b,l,r))+1);
        }
        if(l<r){
            i64 lb=l,ub=r;
            while(ub-lb>1){
                i64 mid=(lb+ub)/2;
                if(rec(t,b,l,mid)<=rec(t,b,mid+1,r)) lb=mid;
                else ub=mid;
            }
            chmin(res,max(rec(t,b,l,lb),rec(t,b,lb+1,r))+1);
        }
        return memo[s]=res;
    };

    cout << rec(0,H-1,0,W-1) << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Compiler output:
a.cc: In function 'void solve()':
a.cc:93:28: error: use of deleted function 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::tuple<long int, long int, long int, long int>; _Tp = long int; _Hash = std::hash<std::tuple<long int, long int, long int, long int> >; _Pred = std::equal_to<std::tuple<long int, long int, long int, long int> >; _Alloc = std::allocator<std::pair<const std::tuple<long int, long int, long int, long int>, long int> >]'
   93 |     unordered_map<tup,i64> memo;
      |                            ^~~~
In file included from /usr/include/c++/14/unordered_map:41,
                 from /usr/include/c++/14/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:53,
                 from a.cc:1:
/usr/include/c++/14/bits/unordered_map.h:148:7: note: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map() [with _Key = std::tuple<long int, long int, long int, long int>; _Tp = long int; _Hash = std::hash<std::tuple<long int, long int, long int, long int> >; _Pred = std::equal_to<std::tuple<long int, long int, long int, long int> >; _Alloc = std::allocator<std::pair<const std::tuple<long int, long int, long int, long int>, long int> >]' is implicitly deleted because the default definition would be ill-formed:
  148 |       unordered_map() = default;
      |       ^~~~~~~~~~~~~
/usr/include/c++/14/bits/unordered_map.h: At global scope:
/usr/include/c++/14/bits/unordered_map.h:148:7: error: use of deleted function 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::tuple<long int, long int, long int, long int>; _Value = std::pair<const std::tuple<long int, long int, long int, long int>, long int>; _Alloc = std::allocator<std::pair<const std::tuple<long int, long int, long int, long int>, long int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::tuple<long int, long int, long int, long int> >; _Hash = std::hash<std::tuple<long int, long int, long int, long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/14/bits/unordered_map.h:33:
/usr/include/c++/14/bits/hashtable.h:539:7: note: 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::tuple<long int, long int, long int, long int>; _Value = std::pair<const std::tuple<long int, long int, long int, long int>, long int>; _Alloc = std::allocator<std::pair<const std::tuple<long int, long int, long int, long int>, long int> >; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::tuple<long int, long int, long int, long int> >; _Hash = std::hash<std::tuple<long int, long int, long int, long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
  539 |       _Hashtable() = default;
      |       ^~~~~~~~~~
/usr/include/c++/14/bits/hashtable.h:539:7: error: use of deleted function 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::tuple<long int, long int, long int, long int>; _Value = std::pair<const std::tuple<long int, long int, long int, long int>, long int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::tuple<long int, long int, long int, long int> >; _Hash = std::hash<std::tuple<long int, long int, long int, long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]'
In file included from /usr/include/c++/14/bits/hashtable.h:35:
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: note: 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _Traits>::_Hashtable_base() [with _Key = std::tuple<long int, long int, long int, long int>; _Value = std::pair<const std::tuple<long int, long int, long int, long int>, long int>; _ExtractKey = std::__detail::_Select1st; _Equal = std::equal_to<std::tuple<long int, long int, long int, long int> >; _Hash = std::hash<std::tuple<long int, long int, long int, long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, false, true>]' is implicitly deleted because the default definition would be ill-formed:
 1731 |       _Hashtable_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1731:7: error: use of deleted function 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::tuple<long int, long int, long int, long int>; _Value = std::pair<const std::tuple<long int, long int, long int, long int>, long int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::tuple<long int, long int, long int, long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]'
/usr/include/c++/14/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<std::tuple<long int, long int, long int, long int> >]':
/usr/include/c++/14/bits/hashtable_policy.h:1328:7:   required from here
 1328 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1245:49: error: use of deleted function 'std::hash<std::tuple<long int, long int, long int, long int> >::hash()'
 1245 |       _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
      |                                                 ^~~~~
In file included from /usr/include/c++/14/string_view:50,
                 from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52:
/usr/include/c++/14/bits/functional_hash.h:102:12: note: 'std::hash<std::tuple<long int, long int, long int, long int> >::hash()' is implicitly deleted because the default definition would be ill-formed:
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:102:12: error: no matching function for call to 'std::__hash_enum<std::tuple<long int, long int, long int, long int>, false>::__hash_enum()'
/usr/include/c++/14/bits/functional_hash.h:83:7: note: candidate: 'std::__hash_enum<_Tp, <anonymous> >::__hash_enum(std::__hash_enum<_Tp, <anonymous> >&&) [with _Tp = std::tuple<long int, long int, long int, long int>; bool <anonymous> = false]'
   83 |       __hash_enum(__hash_enum&&);
      |       ^~~~~~~~~~~
/usr/include/c++/14/bits/functional_hash.h:83:7: note:   candidate expects 1 argument, 0 provided
/usr/include/c++/14/bits/functional_hash.h:102:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::tuple<long int, long int, long int, long int>; bool <anonymous> = false]' is private within this context
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:84:7: note: declared private here
   84 |       ~__hash_enum();
      |       ^
/usr/include/c++/14/bits/hashtable_policy.h:1245:49: note: use '-fdiagnostics-all-candidates' to display considered candidates
 1245 |       _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
      |                                                 ^~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1328:7: note: 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash, _Unused, __cache_hash_code>::_Hash_code_base() [with _Key = std::tuple<long int, long int, long int, long int>; _Value = std::pair<const std::tuple<long int, long int, long int, long int>, long int>; _ExtractKey = std::__detail::_Select1st; _Hash = std::hash<std::tuple<long int, long int, long int, long int> >; _RangeHash = std::__detail::_Mod_range_hashing; _Unused = std::__detail::_Default_ranged_hash; bool __cache_hash_code = true]' is implicitly deleted because the default definition would be ill-formed:
 1328 |       _Hash_code_base() = default;
      |       ^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1328:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::tuple<long int, long int, long int, long int> >, true>::~_Hashtable_ebo_helper()'
/usr/include/c++/14/bits/hashtable_policy.h:1242:12: note: 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::tuple<long int, long int, long int, long int> >, true>::~_Hashtable_ebo_helper()' is implicitly deleted because the default definition would be ill-formed:
 1242 |     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
      |            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/hashtable_policy.h:1242:12: error: use of deleted function 'std::hash<std::tuple<long int, long int, long int, long int> >::~hash()'
/usr/include/c++/14/bits/functional_hash.h:102:12: note: 'std::hash<std::tuple<long int, long int, long int, long int> >::~hash()' is implicitly deleted because the default definition would be ill-formed:
  102 |     struct hash : __hash_enum<_Tp>
      |            ^~~~
/usr/include/c++/14/bits/functional_hash.h:102:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::tuple<long int, long int, long int, long int>; bool <anonymous> = false]' is private within this context
/usr/include/c++/14/bits/functional_hash.h:84:7: note: declared private here
   84 |       ~__hash_enum();
      |       ^
/usr/include/c++/14/bits/hashtable_policy