結果

問題 No.1668 Grayscale
ユーザー 👑 obakyanobakyan
提出日時 2021-09-12 21:48:13
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 1,849 ms / 4,000 ms
コード長 1,407 bytes
コンパイル時間 311 ms
コンパイル使用メモリ 5,288 KB
実行使用メモリ 113,620 KB
最終ジャッジ日時 2023-09-06 23:08:07
合計ジャッジ時間 7,685 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,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1,106 ms
113,620 KB
testcase_07 AC 1,102 ms
113,596 KB
testcase_08 AC 324 ms
26,956 KB
testcase_09 AC 1,849 ms
111,588 KB
testcase_10 AC 542 ms
31,784 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 4 ms
4,376 KB
testcase_13 AC 74 ms
9,236 KB
testcase_14 AC 286 ms
24,556 KB
testcase_15 AC 122 ms
12,540 KB
testcase_16 AC 68 ms
7,596 KB
testcase_17 AC 52 ms
7,440 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 5 ms
4,376 KB
testcase_21 AC 5 ms
4,380 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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]])
0