Language: C++

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = int_fast64_t;
using pll = pair<ll,ll>;
constexpr ll INF = (1LL<<60);
constexpr ll MOD = (1e9+7);
//constexpr ll MOD = (998244353);
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
#if loc||local
void dump(){cerr<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
void dump(){}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}

main(){
  int h,w,k;
  cin>>h>>w>>k;
  vector<string> s(h);
  cin>>s;
  auto sum = vec<ll>(h+1,w+1);
  rep(i,h)rep(j,w){
    sum[i+1][j+1] = (s[i][j]=='1');
  }
  rep(i,h)rep(j,w){
    sum[i + 1][j + 1] += sum[i + 1][j] + sum[i][j + 1] - sum[i][j];
  }

  auto get = [&](int sy, int sx, int ty, int tx) {
   return sum[ty][tx] - sum[ty][sx] - sum[sy][tx] + sum[sy][sx];
  };
  auto chk = [&](auto const& div,int px,int x){
    int n = div.size();
    ll tmp = 0;
    rep(i,n-1){
      chmax(tmp,get(div[i],px,div[i+1],x));
    }
    return tmp;
  };
  ll ans = INF;
  for(int i=0;i<(1<<(h-1));++i){
    bitset<11> b(i);
    vector<ll> div;
    div.emplace_back(0);
    rep(j,10)if(b[j])div.emplace_back(j+1);
    div.emplace_back(h);
    int px=0;
    ll tmp=b.count();
    for(int x=1;x<=w;++x){
      auto x = chk(div,px,y);
      if(x>k){
        if(abs(x-px)==1){
          tmp = INF;
          break;
        }
        tmp++;
        px = x-1;
      }
    }
    chmin(ans,tmp);
  }
  cout<<(ans)<<endl;
}

signed _main(){

  ll h,w,k;
  cin>>h>>w>>k;
  vector<string> s(h);
  cin>>s;

  if(k==1){
    cout<<h+w-2<<endl;
    return 0;
  }
  if(k==h*w){
    cout<<0<<endl;
    return 0;
  }

  auto a = vec<ll>(h,w);
  rep(i,h)rep(j,w){
    a.at(i).at(j) = (s.at(i).at(j)=='0'?0:1);
  }
  auto sum = vec<ll>(h+1,w+1);
  rep(i,h)rep(j,w){
    sum[i+1][j+1] = sum[i+1][j]+a[i][j];
  }
  rep(i,h)rep(j,w){
    sum[i+1][j+1] += sum[i][j+1];
  }

  auto get = [&](ll sy,ll sx,ll gy,ll gx){
    dump(sy,sx,gy,gx);
    return sum.at(gy).at(gx)-sum.at(gy).at(sx)-sum.at(sy).at(gx)+sum.at(sy).at(sx);
  };

  auto is_ok = [&](auto const& div,ll y,ll px){
    dump("div: ",div);
    ll tmp = 0;
    ll n = div.size();
    rep(i,n-1){
      chmax(tmp,get(div.at(i),px,div.at(i+1),y));
    }
    return tmp<=k;
  };

  ll ans = INF;
  for(ll bit=0;bit<(1<<(h-1));++bit){
    bitset<10> b(bit);
    vector<ll> div;
    div.emplace_back(0);
    rep(i,h)if(b[i])div.emplace_back(i+1);
    div.emplace_back(h);
    ll px = 0;
    ll tmp = div.size()-2;
    for(ll y=1;y<=w;++y){
      if(!is_ok(div,y,px)){
        if(abs(y-px)==1){
          tmp=INF;
          break;
        }
        tmp++;
        px = y-1;
      }
    }
    if(px==w-1)tmp++;
    chmin(ans,tmp);
  }
  cout<<(ans)<<endl;

}

Compiler output:
a.cc:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~
a.cc: In function 'int main()':
a.cc:60:12: error: redeclaration of 'auto x'
   60 |       auto x = chk(div,px,y);
      |            ^
a.cc:59:13: note: 'int x' previously declared here
   59 |     for(int x=1;x<=w;++x){
      |             ^
a.cc:60:27: error: 'y' was not declared in this scope
   60 |       auto x = chk(div,px,y);
      |                           ^
a.cc: In function 'int _main()':
a.cc:142:1: warning: control reaches end of non-void function [-Wreturn-type]
  142 | }
      | ^