import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } /* 0 1 2 3 4 5 6 7 +----------------------- 0| 0 1 1 1 1 1 1 1 1| 1 3 5 7 9 11 13 15 2| 1 5 6 9 11 13 3| 1 7 9 13 17 */ long solve(long m, long n) { if (m > n) { swap(m, n); } if (m == n) { if (m % 2 == 0) { return m * m + m; } else { return m * m + m + 1; } } else { if (m % 2 == 0) { if (n % 2 == 0) { return m * n + m + 1; } else { return m * n + m + 1; } } else { if (n % 2 == 0) { return m * n + n + 1; } else { return m * n + n + 1; } } } } void main() { debug { foreach (m; 0 .. 8) { foreach (n; 0 .. 8) { writef("%2d ", solve(m, n)); } writeln(); } return; } debug { foreach (m; 1 .. 9) foreach (n; 1 .. 9) { if (m * n <= 20) { auto dp = new int[][][](1 << (m * n), m * n, 2); foreach (p; 0 .. 1 << (m * n)) { foreach (z; 0 .. m * n) { dp[p][z][] = -1; } } foreach (z; 0 .. m * n) { dp[1 << z][z][] = 0; } foreach (p; 0 .. 1 << (m * n)) { foreach (z; 0 .. m * n) { foreach (s; 0 .. 2) { if (dp[p][z][0] >= 0) { const y = z % n; { int q = p; foreach (x; z / n + 1 .. m) { if ((p >> (x * n + y)) & 1) { break; } q |= 1 << (x * n + y); chmax(dp[q][x * n + y][1], dp[p][z][0] + 1); } } { int q = p; foreach_reverse (x; 0 .. z / n) { if ((p >> (x * n + y)) & 1) { break; } q |= 1 << (x * n + y); chmax(dp[q][x * n + y][1], dp[p][z][0] + 1); } } } if (dp[p][z][1] >= 0) { const x = z / n; { int q = p; foreach (y; z % n + 1 .. n) { if ((p >> (x * n + y)) & 1) { break; } q |= 1 << (x * n + y); chmax(dp[q][x * n + y][0], dp[p][z][1] + 1); } } { int q = p; foreach_reverse (y; 0 .. z % n) { if ((p >> (x * n + y)) & 1) { break; } q |= 1 << (x * n + y); chmax(dp[q][x * n + y][0], dp[p][z][1] + 1); } } } } } } int mx; foreach (z; 0 .. m * n) { chmax(mx, dp[$ - 1][z].maxElement); } writeln(m, " ", n, ": ", mx); stdout.flush; } } return; } try { for (; ; ) { const M = readLong(); const N = readLong(); const ans = solve(M, N); writeln(ans); } } catch (EOFException e) { } }