import java.util.Scanner; // 严格遵守OJ要求：仅Main类，无多余导入/代码 public class Main { // 全局变量：网格行列、最大放置数、网格标记（单全局网格，零拷贝回溯） private static int n, m, maxCnt = 0; private static boolean[][] grid; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); sc.close(); grid = new boolean[n][m]; dfs(0, 0, 0); // 从(0,0)开始，已放置0个 System.out.println(maxCnt); } /** * 逐格DFS核心：极致剪枝+零拷贝回溯+斜相邻冲突判断 * @param i 当前行 * @param j 当前列 * @param cur 当前已放置数量 */ private static void dfs(int i, int j, int cur) { // 终极剪枝：当前数 + 剩余格子数 ≤ 最大值，直接终止（无任何继续的意义） int remain = n * m - (i * m + j); if (cur + remain <= maxCnt) { return; } // 递归终止：遍历完所有行，更新最大值 if (i >= n) { if (cur > maxCnt) { maxCnt = cur; } return; } // 处理换行：当前列越界则跳转到下一行第0列 int nextI = i, nextJ = j + 1; if (nextJ >= m) { nextI = i + 1; nextJ = 0; } // 优化遍历顺序：优先放置（更快找到最优解，让剪枝更早生效） if (canPut(i, j)) { grid[i][j] = true; // 标记放置 dfs(nextI, nextJ, cur + 1); // 递归下一个格子 grid[i][j] = false; // 回溯：仅修改单个格子，零开销 } // 后尝试不放置 dfs(nextI, nextJ, cur); } /** * 核心判断：当前格子(i,j)是否可放（仅4个斜相邻无据点） * 无任何冗余判断，直接返回结果 */ private static boolean canPut(int i, int j) { // 上左 if (i > 0 && j > 0 && grid[i-1][j-1]) return false; // 上右 if (i > 0 && j < m-1 && grid[i-1][j+1]) return false; // 下左 if (i < n-1 && j > 0 && grid[i+1][j-1]) return false; // 下右 if (i < n-1 && j < m-1 && grid[i+1][j+1]) return false; return true; } }