結果
問題 | No.1701 half price |
ユーザー |
👑 |
提出日時 | 2022-01-09 20:25:11 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 40 ms / 3,000 ms |
コード長 | 1,458 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 6,820 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 10:30:00 |
合計ジャッジ時間 | 1,265 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
local bls, brs = bit.lshift, bit.rshiftlocal bxor = bit.bxorlocal 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 = 0local total = bls(1, size) - 1local bpos = {}for i = 1, size dobpos[bls(1, i - 1)] = iendwork_func()for i = 1, total dolocal v = grayCode(i)if prv < v thenprv, v = v, v - prvadd_func(bpos[v])elseprv, v = v, prv - vrm_func(bpos[v])endwork_func()endendlocal n, w = io.read("*n", "*n")local a = {}for i = 1, n doa[i] = io.read("*n")endlocal ret = 0local box = {}local subbox = {}local subcnt = 0local subv = 0local f = falselocal function subadd(idx)subv = subv - brs(a[subbox[idx]], 1)endlocal function subrm(idx)subv = subv + brs(a[subbox[idx]], 1)endlocal function subwork()if w == subv thenf = trueendendfor i = 1, n do box[i] = false endlocal function add_func(idx)box[idx] = trueendlocal function rm_func(idx)box[idx] = falseendlocal function work_func()subcnt = 0subv = 0f = falsefor i = 1, n doif box[i] thensubcnt = subcnt + 1subbox[subcnt] = isubv = subv + a[i]endendgrayWalk(subcnt, subadd, subrm, subwork)if f then ret = ret + 1 endendgrayWalk(n, add_func, rm_func, work_func)if w == 0 then ret = ret - 1 endprint(ret)