結果
問題 | No.1360 [Zelkova 4th Tune] 協和音 |
ユーザー |
👑 |
提出日時 | 2021-01-22 21:30:46 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 1,579 bytes |
コンパイル時間 | 261 ms |
コンパイル使用メモリ | 6,948 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-27 21:42:07 |
合計ジャッジ時間 | 4,626 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
local mmi, mma = math.min, math.max local bls, brs = bit.lshift, bit.rshift local bxor = bit.bxor local function grayCode(x) return bxor(x, brs(x, 1)) end -- add_func(idx), rm_func(idx), work_func() local function grayWalk(size, add_func, rm_func, work_func) local prv = 0 local total = bls(1, size) - 1 local bpos = {} for i = 1, size do bpos[bls(1, i - 1)] = i end -- if need first work then use below -- work_func() for i = 1, total do local v = grayCode(i) if prv < v then prv, v = v, v - prv add_func(bpos[v]) else prv, v = v, prv - v rm_func(bpos[v]) end work_func() end end local n = io.read("*n") local a = {} for i = 1, n do a[i] = io.read("*n") end local b = {} for i = 1, n do b[i] = {} for j = 1, n do b[i][j] = io.read("*n") end end local maxboxsize = 0 local maxbox = {} local maxscore = -1 local score = 0 local box = {} local function add_func(idx) score = score + a[idx] for i = 1, #box do score = score + b[box[i]][idx] end table.insert(box, idx) end local function rm_func(idx) score = score - a[idx] for i = #box, 1, -1 do score = score - b[box[i]][idx] if box[i] == idx then table.remove(box, i) end end end local function work_func() if maxscore < score then maxscore = score maxboxsize = #box for i = 1, maxboxsize do maxbox[i] = box[i] end end end grayWalk(n, add_func, rm_func, work_func) print(maxscore) for i = maxboxsize + 1, #maxbox do table.remove(maxbox) end table.sort(maxbox) print(table.concat(maxbox, " "))