提出 #8876240

ソースコード 拡げる

require "big"
h, w = read_line.split.map(&.to_i)
board = [] of Array(Int16)
h.times do
  board << read_line.split.map(&.to_i16)
end
h.times do |i|
  line = board[i]
  read_line.split.map(&.to_i16).each_with_index do |b, j|
    line[j] = (line[j] - b).abs
  end
end
dpss = [] of Array(BigInt)
h.times do |y|
  dps = [] of BigInt
  dpss << dps
  w.times do |x|
    dp = BigInt.new
    c = board[y][x]
    if x == 0 && y == 0
      dp |= 1.to_big_i << (c + 15000)
    else
      if x != 0
        dp |= (dpss[y][x - 1] << c) | (dpss[y][x - 1] >> c)
      end
      if y != 0
        dp |= (dpss[y - 1][x] << c) | (dpss[y - 1][x] >> c)
      end
    end
    dps << dp
  end
end
p (0..30000).select {|i| dpss[h - 1][w - 1].bit(i) == 1}.min_of {|b| (15000 - b).abs}

提出情報

提出日時
問題 E - Balanced Path
ユーザ hakatashi
言語 Crystal (0.20.5)
得点 500
コード長 791 Byte
結果 AC
実行時間 211 ms
メモリ 56316 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 2
AC × 25
セット名 テストケース
Sample sample_01, sample_02
All hand_01, hand_02, hand_03, hand_04, hand_05, hand_06, max_01, max_02, max_03, max_04, max_05, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, sample_01, sample_02
ケース名 結果 実行時間 メモリ
hand_01 AC 112 ms 29692 KiB
hand_02 AC 110 ms 29692 KiB
hand_03 AC 110 ms 29692 KiB
hand_04 AC 111 ms 29564 KiB
hand_05 AC 108 ms 29692 KiB
hand_06 AC 111 ms 29692 KiB
max_01 AC 167 ms 47612 KiB
max_02 AC 113 ms 29692 KiB
max_03 AC 114 ms 31612 KiB
max_04 AC 111 ms 29692 KiB
max_05 AC 196 ms 56316 KiB
random_01 AC 92 ms 29564 KiB
random_02 AC 88 ms 22396 KiB
random_03 AC 101 ms 29564 KiB
random_04 AC 92 ms 29564 KiB
random_05 AC 60 ms 16892 KiB
random_06 AC 210 ms 56188 KiB
random_07 AC 209 ms 56316 KiB
random_08 AC 208 ms 56316 KiB
random_09 AC 211 ms 56188 KiB
random_10 AC 209 ms 56188 KiB
random_11 AC 204 ms 56188 KiB
random_12 AC 206 ms 56188 KiB
sample_01 AC 24 ms 892 KiB
sample_02 AC 25 ms 892 KiB