Language: C++

// Beginner159.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <climits>
#include <vector>

using namespace  std;

typedef  long long ll;

bool is_strong_pa(const string& s, int from, int to)
{
	bool is_pal = true;

	for (int i = from; i <= (to - from) / 2; ++i)
	{
		if (s[i] != s[to - i])
		{
			is_pal = false;
			break;
		}
	}

	return is_pal;
}

int get_white_count(const vector<string>& grid, int r0, int r1, int c0, int c1)
{
	int count = 0;
	for (int i = r0; i < r1; ++i)
	{
		for (int j = c0; j < c1; ++j)
		{
			if (grid[i][j] == '1') count++;
		}
	}
	return count;
}


const int H_MAX = 12;
const int W_MAX = 1002;
int dp[H_MAX][W_MAX][H_MAX][W_MAX];

int bit_count(int value)
{
	int count = 0;
	while (value > 0)
	{
		if ((value & 1) == 1) count++;
		value >>= 1;
	}
	return count;
}


int get_next_1_bit_pos(int value, int pos, int& i)
{


	while (i < value)
	{

		i = i == 0 ? 1 : i << 1;
		pos++;
		if (value & i) return pos;


	}
	return  -1;
}

vector<int> get_all_positions(int value)
{
	vector<int> positions;
	int pos = 0;
	int i = 0;
	while (true)
	{
		pos = get_next_1_bit_pos(value, pos, i);

		if (pos == -1) break;
		
		positions.push_back(pos);
	}
	
	return positions;
}

int get_min_greedy_bit_mask(int H, int W, int K, const vector<string>& grid)
{
	int splits = static_cast<int>(pow(2, H - 1));
	int min_splits = INT_MAX;
	for (int i = 0; i < splits; ++i)
	{
		const auto positions = get_all_positions(i);
		const int size = positions.size();
		int cuts = size;
		
		int prev_col_cut = 0;

		bool got_new_cut = true;

		while (got_new_cut)
		{
			got_new_cut = false;
			for (int c = prev_col_cut + 1; c <= W; ++c)
			{
			
				for (int r = -1; r < size; ++r)
				{
					const auto r0 = r == -1 ? 0 : positions[r];
					const auto r1 = r == size - 1 ? H : positions[r + 1];

					if (dp[r0][prev_col_cut][r1][c] == -INT_MAX)
					{
						dp[r0][prev_col_cut][r1][c] = get_white_count(grid, r0, r1, prev_col_cut, c);
					}

					if (dp[r0][prev_col_cut][r1][c] > K)
					{
						if (c == prev_col_cut - 1) return INT_MAX;

						got_new_cut = true;
						cuts++;
						prev_col_cut = c - 1;


						break;
					}
				}
				if (got_new_cut) break;
			}
		}
		if (cuts < min_splits) min_splits = cuts;
	}
	return min_splits;
}





int get_min_greedy(const vector<int>& row_cuts, int rows, int H, int W, int K, const vector<string>& grid)
{
	if (rows == H - 1) //max row cuts
	{
		const int size = static_cast<int>(row_cuts.size());
		int cuts = size;
		int prev_col_cut = 0;

		bool got_new_cut = true;

		while (got_new_cut)
		{
			got_new_cut = false;
			for (int c = prev_col_cut + 1; c <= W; ++c)
			{
				for (int r = -1; r < size; ++r)
				{
					const auto r0 = r == -1 ? 0 : row_cuts[r];
					const auto r1 = r == size - 1 ? H : row_cuts[r + 1];
					
					if (dp[r0][prev_col_cut][r1][c] == -INT_MAX)
					{
						dp[r0][prev_col_cut][r1][c] = get_white_count(grid, r0, r1, prev_col_cut, c);
					}

					if (dp[r0][prev_col_cut][r1][c] > K)
					{
						if (c == prev_col_cut - 1) return INT_MAX;

						got_new_cut = true;
						cuts++;
						prev_col_cut = c - 1;


						break;
					}
				}
				if (got_new_cut) break;
			}
		}

		return cuts;
	}

	auto rc0 = row_cuts;
	auto rc1 = row_cuts;
	rc1.push_back(rows + 1);

	return min(
		get_min_greedy(rc0, rows + 1, H, W, K, grid),
		get_min_greedy(rc1, rows + 1, H, W, K, grid));
}

int main()
{
	/*int n = 37;
	int pos = 0;
	int i = 0;
	while (pos != -1)
	{
		pos = get_next_1_bit_pos(n, pos, i);
		cout << pos << "\n";
	}*/
	
	/*int n, m;
	cin >> n >> m;

	int sum = 0;
	sum += n * (n - 1) / 2;
	sum += m * (m - 1) / 2;
	cout << sum;*/

	/*string s;
	cin >> s;

	const int n = s.length();

	bool is_pal = is_strong_pa(s, 0, n - 1) &&
		is_strong_pa(s, 0, (n - 1) / 2 - 1) &&
		is_strong_pa(s, (n + 3) / 2 - 1, n - 1);

	cout << (is_pal ? "Yes" : "No");*/

	/*int l;
	cin >> l;

	double side = 1.0*l / 3;
	double res = side * side * side;

	cout.precision(10);

	cout << res;*/



	/*ll n, ai;
	cin >> n;
	vector<ll> a(n);
	map<ll, ll> numbers;

	for (int i = 0; i < n; ++i)
	{
		cin >> ai;
		a[i] = ai;
		numbers[ai]++;
	}

	ll sum = 0;
	for (const auto& item: numbers)
	{
		ll count = item.second;
		sum += count * (count - 1) / 2;
	}

	for (int i = 0; i < n; ++i)
	{
		ll count = numbers[a[i]];
		cout << (sum - (count-1)) << "\n";
	}*/

	//E

	
	int H, W, K;
	cin >> H >> W >> K;
	vector<string> grid(H);
	string s;
	for (int i = 0; i < H; ++i)
	{
		cin >> s;
		grid[i] = s;
	}


	for (int i = 0; i <= H; ++i)
	{
		for (int j = 0; j <= W; ++j)
		{
			for (int k = 0; k <= H; ++k)
			{
				for (int l = 0; l <= W; ++l)
				{
					dp[i][j][k][l] = -INT_MAX;
				}
			}
		}
	}

	int res = get_min_greedy_bit_mask(H, W, K, grid);
	cout << res;
	

	//int res = get_min_greedy({}, 0, H, W, K, grid);
	//cout << res;

	//const int MOD = 998244353;
	//int n, S;
	//cin >> n >> S;
	//vector<int> a(n);
	//int ai;
	//for (int i = 0; i < n; ++i)
	//{
	//	cin >> ai;
	//	a[i] = ai;
	//}

	//const int nax = 301;
	//vector<vector<vector<int>>>dp(n, vector<vector<int>>(n, vector<int>(S+1, 0)));

	//ll sum = 0;

	//for (int l = n-1; l >= 0; --l)
	//{
	//	for (int r = l; r < n; ++r)
	//	{
	//		for (int s = 0; s <= S; ++s)
	//		{
	//			if (s == 0) dp[l][r][s] = 1;
	//			else if (l == r) dp[l][r][s] = a[l] == s ? 1 : 0;
	//			else
	//			{
	//				dp[l][r][s] = dp[l][r - 1][s];
	//				if (s - a[r] >= 0)
	//				{
	//					dp[l][r][s] += dp[l][r - 1][s - a[r]];
	//				}
	//				/*if (s-a[l] >= 0)
	//				{
	//					dp[l][r][s] += dp[l + 1][r][s - a[l]];
	//				}*/
	//			}

	//			if (s == S)
	//			{
	//				sum = (sum + dp[l][r][s]) % MOD;
	//			}
	//		}
	//	}
	//}

	//cout << sum;

}



Compiler output:
a.cc: In function 'int get_min_greedy_bit_mask(int, int, int, const std::vector<std::__cxx11::basic_string<char> >&)':
a.cc:96:39: error: 'pow' was not declared in this scope
   96 |         int splits = static_cast<int>(pow(2, H - 1));
      |                                       ^~~