結果
問題 |
No.1606 Stuffed Animals Keeper
|
ユーザー |
👑 |
提出日時 | 2021-07-19 23:54:14 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 32 ms / 3,000 ms |
コード長 | 1,029 bytes |
コンパイル時間 | 37 ms |
コンパイル使用メモリ | 6,812 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-17 13:37:24 |
合計ジャッジ時間 | 1,884 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 48 |
ソースコード
local mfl, mce = math.floor, math.ceil local mmi, mma = math.min, math.max local n = io.read("*n") local a, b = {}, {} a[1], b[1] = 0, 0 for i = 1, n do local v = io.read("*n") if v == 0 then a[#a] = a[#a] + 1 elseif v == 1 then b[#b] = b[#b] + 1 else table.insert(a, 0) table.insert(b, 0) end end n = #a local dp1, dp2 = {}, {} local minval = 0 local maxval = 0 dp1[1] = 0 local inf = 1000000007 for i = 1, n do local src = i % 2 == 1 and dp1 or dp2 local dst = i % 2 == 1 and dp2 or dp1 local nxtmin = minval - a[i] local nxtmax = maxval + b[i] for j = nxtmin, nxtmax do dst[j - nxtmin + 1] = inf end for j = minval, maxval do local v = src[j - minval + 1] local d1 = j - a[i] dst[d1 - nxtmin + 1] = mmi(dst[d1 - nxtmin + 1], v + a[i]) local d2 = j + b[i] dst[d2 - nxtmin + 1] = mmi(dst[d2 - nxtmin + 1], v + b[i]) end minval, maxval = nxtmin, nxtmax end local tbl = n % 2 == 1 and dp2 or dp1 local ret = tbl[0 - minval + 1] print(ret < inf and mfl(ret / 2) or -1)