题解：P11464 支配剧场

// #pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

const int N = 50;
const int inf = 1 << 30;
const ll inf64 = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)

int n, m, k, q;
int a[N][N];
vector<pii> tot[N];
bool ban[N];
void toggle(int c)
{
	for (auto [x, y] : tot[c])
		a[x][y] = -a[x][y];
	ban[c] = !ban[c];
}
int highest;
int lowest[N], cnt[N];
bool check()
{
	for (int i = 1; i <= k; i++)
	{
		if (lowest[i] == 0 || ban[i])
			continue;
		int cnt0 = 0;
		for (int j = 0; j < m; j++)
			cnt0 += (a[lowest[i]][j] == i) && (a[lowest[i] - 1][j] > 0);
		if (cnt0 < (cnt[i] + 1) / 2)
			return false;
	}
	for (int j = 0; j < m; j++)
		if (a[highest][j] > 0)
			return true;
	return false;
}
int ans;
void dfs(int x = 1, int cnt = 0)
{
	if (cnt + (k - x + 1) <= ans)
		return;
	if (x == k + 1)
	{
		if (check())
			ans = max(ans, cnt);
		return;
	}
	toggle(x);
	dfs(x + 1, cnt + 1);
	toggle(x);
	dfs(x + 1, cnt);
}
void work()
{
	cin >> n >> m;
	for (int i = n - 1; i >= 0; i--)
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			if (a[i][j])
				highest = max(highest, i);
			k = max(k, a[i][j]);
			if (!a[i][j])
				continue;
			if (lowest[a[i][j]] == i)
				cnt[a[i][j]]++;
			else
			{
				lowest[a[i][j]] = i;
				cnt[a[i][j]] = 1;
			}
			tot[a[i][j]].push_back({i, j});
		}
	dfs();
	cout << ans << endl;
}
int main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	int t = 1;
	while (t-- > 0)
	{
		work();
	}
}