https://www.luogu.com.cn/record/180865343

# include <bits/stdc++.h>

# define I return

# define AK 0

# define IOI ;

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

const bool mp[4][3][3] = {
	{
		{1, 1, 1},
		{0, 1, 0},
		{0, 1, 0}
	},

	{
		{0, 0, 1},
		{1, 1, 1},
		{0, 0, 1}
	},

	{
		{0, 1, 0},
		{0, 1, 0},
		{1, 1, 1}
	},

	{
		{1, 0, 0},
		{1, 1, 1},
		{1, 0, 0}
	}

};

int n, m, maxx[15][15], tot;

bitset <15> vis[15];

bool check (const int x, const int l, const int r) {

	for (int i = 0; i < 3; ++ i)
		for (int j = 0; j < 3; ++ j)
			if (mp[x][i][j] && vis[l - i][r - j])
				return 0;

	return 1;

}

void add (const int x, const int l, const int r) {

	for (int i = 0; i < 3; ++ i)
		for (int j = 0; j < 3; ++ j)
			if (mp[x][i][j])
				vis[l - i][r - j] = 1;

	return ;

}

void del (const int x, const int l, const int r) {

	for (int i = 0; i < 3; ++ i)
		for (int j = 0; j < 3; ++ j)
			if (mp[x][i][j])
				vis[l - i][r - j] = 0;

	return ;

}

void dfs (int x, int y) {
//	cerr << x << ',' << y - 1 << ':' << tot << ',' << maxx[x][y - 1] << '\n';
//	for (int i = 1; i <= n; ++ i, cerr << '\n') for (int j = 1; j <= m; ++ j) cerr << vis[i][j];
	if (y > m)
		++ x, y = 3;

	if (x > n)
		return ;

	if (tot > maxx[x][y])
		maxx[x][y] = tot;

	dfs (x, y + 1);

	for (int i = 0; i < 4; ++ i)
		if (tot >= maxx[x][y] - 1 && check (i, x, y)) {

			maxx[x][y] = ++ tot, add (i, x, y);

			dfs (x, y + 1);

			-- tot, del (i, x, y);

		}

	return ;

}

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	cin >> n >> m;

	dfs (3, 3);

	cout << maxx[n][m];

	I AK IOI

}
/*
4 4
*/