import java.util.Scanner; import java.util.Stack; // 强制主类名Main，严格符合OJ规范 public class Main { // 定义栈中存储的状态类：记录当前行、列、已放数量、网格放置标记 static class State { int i, j, cnt; boolean[][] grid; State(int i, int j, int cnt, boolean[][] grid) { this.i = i; this.j = j; this.cnt = cnt; this.grid = copyGrid(grid); // 深拷贝网格，避免状态污染 } } // 深拷贝网格（状态独立必备） private static boolean[][] copyGrid(boolean[][] original) { if (original == null) return null; boolean[][] copy = new boolean[original.length][original[0].length]; for (int i = 0; i < original.length; i++) { System.arraycopy(original[i], 0, copy[i], 0, original[i].length); } return copy; } // 判断当前格子是否可放（4个斜相邻无据点，核心规则） private static boolean canPut(int i, int j, boolean[][] grid, int n, int m) { 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; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 行 int m = sc.nextInt(); // 列 sc.close(); int max = 0; Stack<State> stack = new Stack<>(); boolean[][] initGrid = new boolean[n][m]; stack.push(new State(0, 0, 0, initGrid)); // 初始状态入栈 while (!stack.isEmpty()) { State cur = stack.pop(); int i = cur.i, j = cur.j, cnt = cur.cnt; boolean[][] grid = cur.grid; // 剪枝：剩余格子+当前数 ≤ 最大值，直接跳过（核心优化） int remain = n * m - (i * m + j); if (cnt + remain <= max) continue; // 遍历完所有行，更新最大值 if (i >= n) { if (cnt > max) max = cnt; continue; } // 处理换行 int ni = i, nj = j + 1; if (nj >= m) { ni = i + 1; nj = 0; } // 选择1：当前格子不放，直接入栈下一个状态 stack.push(new State(ni, nj, cnt, grid)); // 选择2：当前格子可放则放置，入栈新状态 if (canPut(i, j, grid, n, m)) { grid[i][j] = true; stack.push(new State(ni, nj, cnt + 1, grid)); } } System.out.println(max); // 仅输出结果，无多余字符 } }