結果

問題 No.540 格子点と経路
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-06-03 05:06:11
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,321 bytes
コンパイル時間 715 ms
コンパイル使用メモリ 106,504 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-04 01:30:56
合計ジャッジ時間 2,370 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,384 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 1 ms
4,380 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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) {
  }
}
0