#467005 (Lua) No.545 ママの大事な二人の子供

• 問題: No.545 ママの大事な二人の子供
• ユーザー: 👑 obakyan
• 提出日時: 2020-04-19 16:29:54
• 言語: Lua (LuaJit 2.1.1696795921)
• 結果: AC
• 実行時間: 85 ms / 2,000 ms
• コード長: 1,532 bytes
• コンパイル時間: 126 ms
• コンパイル使用メモリ: 6,812 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-15 16:36:22
• 合計ジャッジ時間: 2,126 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	3 ms; 5,376 KB
testcase_13	AC	6 ms; 5,376 KB
testcase_14	AC	9 ms; 5,376 KB
testcase_15	AC	2 ms; 5,376 KB
testcase_16	AC	16 ms; 5,376 KB
testcase_17	AC	48 ms; 5,376 KB
testcase_18	AC	51 ms; 5,376 KB
testcase_19	AC	51 ms; 5,376 KB
testcase_20	AC	51 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	59 ms; 5,376 KB
testcase_23	AC	85 ms; 5,376 KB
testcase_24	AC	55 ms; 5,376 KB
testcase_25	AC	78 ms; 5,376 KB
testcase_26	AC	84 ms; 5,376 KB
testcase_27	AC	66 ms; 5,376 KB
testcase_28	AC	84 ms; 5,376 KB
testcase_29	AC	76 ms; 5,376 KB
testcase_30	AC	81 ms; 5,376 KB
testcase_31	AC	81 ms; 5,376 KB

ソースコード

local mmi, mma = math.min, math.max
local mab = math.abs
local bls, brs = bit.lshift, bit.rshift
local mfl = math.floor

local function comp(a, b)
  return a < b
end

local function lower_bound(ary, x)
  local num = #ary
  if num == 0 then return 1 end
  if not comp(ary[1], x) then return 1 end
  if comp(ary[num], x) then return num + 1 end
  local min, max = 1, num
  while 1 < max - min do
    local mid = mfl((min + max) / 2)
    if comp(ary[mid], x) then
      min = mid
    else
      max = mid
    end
  end
  return max
end

local n = io.read("*n")
local t = {}
local tgt = 0
for i = 1, n do
  local a, b = io.read("*n", "*n")
  tgt = tgt + a
  t[i] = a + b
end
if n <= 16 then
  local ret = tgt
  local tot = 2^n
  for it = 0, tot - 1 do
    local z = 0
    for i = 1, n do
      if it % 2 == 1 then z = z + t[i] end
      it = brs(it, 1)
    end
    ret = mmi(ret, mab(tgt - z))
  end
  print(ret)
else
  local first = {}
  for it = 0, 65535 do
    local z = 0
    for i = 1, 16 do
      if it % 2 == 1 then z = z + t[i] end
      it = brs(it, 1)
    end
    table.insert(first, z)
  end
  local ret = tgt
  table.sort(first)
  local remtot = 2^(n - 16)
  for it = 0, remtot - 1 do
    local z = 0
    for i = 17, n do
      if it % 2 == 1 then z = z + t[i] end
      it = brs(it, 1)
    end
    local pos = lower_bound(first, tgt - z)
    if pos <= #first then
      ret = mmi(ret, mab(tgt - first[pos] - z))
    end
    if 1 < pos then
      ret = mmi(ret, mab(tgt - first[pos - 1] - z))
    end
  end
  print(ret)
end