結果
問題 | No.50 おもちゃ箱 |
ユーザー |
👑 |
提出日時 | 2020-05-05 20:43:37 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 2,057 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 6,816 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-27 03:28:14 |
合計ジャッジ時間 | 1,641 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
local bls, brs = bit.lshift, bit.rshift local n = io.read("*n") local a = {} for i = 1, n do a[i] = io.read("*n") end local m = io.read("*n") local b = {} for i = 1, m do b[i] = io.read("*n") end table.sort(b, function(x, y) return x > y end) local tot = bls(1, n) local box_index, box_offset = {}, {} local stagetask = {} for i = 1, n do stagetask[i] = {} end for i = 1, tot - 1 do -- set empty state box_index[i] = 11 box_offset[i] = 0 end for i = 1, tot - 1 do local ti = i local cnt = 0 for j = 1, n do if ti % 2 == 1 then cnt = cnt + 1 ti = ti - 1 end ti = ti / 2 end table.insert(stagetask[cnt], i) end -- set first state do local tmp = 1 for i = 1, n do if a[i] <= b[1] then box_index[tmp] = 1 box_offset[tmp] = a[i] end tmp = tmp * 2 end end for stage = 1, n - 1 do local stlen = #stagetask[stage] for i_stagetask = 1, stlen do local used = stagetask[stage][i_stagetask] local bi = box_index[used] if bi <= m then local mul = 1 local tmp = used for j = 1, n do if tmp % 2 == 0 then if box_offset[used] + a[j] <= b[bi] then if bi < box_index[used + mul] then box_index[used + mul] = bi box_offset[used + mul] = box_offset[used] + a[j] elseif bi == box_index[used + mul] and box_offset[used] + a[j] < box_offset[used + mul] then box_offset[used + mul] = box_offset[used] + a[j] end elseif bi ~= m and a[j] <= b[bi + 1] then if bi + 1 < box_index[used + mul] then box_index[used + mul] = bi + 1 box_offset[used + mul] = a[j] elseif bi + 1 == box_index[used + mul] and a[j] < box_offset[used + mul] then box_offset[used + mul] = a[j] end end else tmp = tmp - 1 end tmp = tmp / 2 mul = mul * 2 end end end end print(box_index[tot - 1] <= m and box_index[tot - 1] or -1)