#699241 (Lua) No.1668 Grayscale

• 問題: No.1668 Grayscale
• ユーザー: 👑 obakyan
• 提出日時: 2021-09-12 21:48:13
• 言語: Lua (LuaJit 2.1.1696795921)
• 結果: AC
• 実行時間: 1,745 ms / 4,000 ms
• コード長: 1,407 bytes
• コンパイル時間: 307 ms
• コンパイル使用メモリ: 6,944 KB
• 実行使用メモリ: 145,280 KB
• 最終ジャッジ日時: 2024-06-24 17:11:31
• 合計ジャッジ時間: 7,182 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	0 ms; 5,376 KB
testcase_06	AC	900 ms; 145,272 KB
testcase_07	AC	868 ms; 145,280 KB
testcase_08	AC	338 ms; 27,212 KB
testcase_09	AC	1,745 ms; 142,144 KB
testcase_10	AC	523 ms; 32,836 KB
testcase_11	AC	3 ms; 6,940 KB
testcase_12	AC	4 ms; 6,940 KB
testcase_13	AC	63 ms; 11,456 KB
testcase_14	AC	256 ms; 30,272 KB
testcase_15	AC	114 ms; 14,528 KB
testcase_16	AC	68 ms; 8,640 KB
testcase_17	AC	51 ms; 9,028 KB
testcase_18	AC	1 ms; 6,940 KB
testcase_19	AC	1 ms; 6,944 KB
testcase_20	AC	5 ms; 6,940 KB
testcase_21	AC	7 ms; 6,940 KB
testcase_22	AC	1 ms; 6,944 KB
testcase_23	AC	2 ms; 6,940 KB

ソースコード

local mfl, mce = math.floor, math.ceil
local mmi, mma = math.min, math.max
local h, w, cn = io.read("*n", "*n", "*n")
local n = h * w
local t = {}
local cmap = {}
local cuniq = {}
for i = 1, h do
  for j = 1, w do
    local col = io.read("*n")
    t[(i - 1) * w + j] = col
    cmap[col] = true
  end
end
for k, v in pairs(cmap) do table.insert(cuniq, k) end
table.sort(cuniq)
cn = #cuniq
for i = 1, cn do
  cmap[cuniq[i]] = i
end

for i = 1, n do
  t[i] = cmap[t[i]]
end

local cpos = {}
for i = 1, cn do
  cpos[i] = {}
end
for i = 1, n do
  table.insert(cpos[t[i]], i)
end
local ret = {}
for i = 1, n do ret[i] = -1 end
for i = 1, #cpos[1] do
  ret[cpos[1][i]] = 1
end
for i = 2, cn do
  local v = ret[cpos[i - 1][1]]
  for j = 1, #cpos[i] do
    local pos = cpos[i][j]
    local row = mce(pos / w)
    local col = pos - (row - 1) * w
    if 1 < row and t[pos - w] < t[pos] then
      v = mma(v, 1 + ret[pos - w])
    end
    if row < h and t[pos + w] < t[pos] then
      v = mma(v, 1 + ret[pos + w])
    end
    if 1 < col and t[pos - 1] < t[pos] then
      v = mma(v, 1 + ret[pos - 1])
    end
    if col < w and t[pos + 1] < t[pos] then
      v = mma(v, 1 + ret[pos + 1])
    end
  end
  for j = 1, #cpos[i] do
    ret[cpos[i][j]] = v
  end
end
-- for i = 1, h do
  -- for j = 1, w do
    -- io.write(ret[(i - 1) * w + j])
    -- io.write(j == w and "\n" or " ")
  -- end
-- end
print(ret[cpos[cn][1]])