結果

問題 No.60 魔法少女
ユーザー 👑 obakyanobakyan
提出日時 2019-05-03 21:00:58
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 2,349 ms / 5,000 ms
コード長 3,173 bytes
コンパイル時間 126 ms
コンパイル使用メモリ 5,308 KB
実行使用メモリ 15,780 KB
最終ジャッジ日時 2023-08-30 05:53:42
合計ジャッジ時間 14,074 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
10,616 KB
testcase_01 AC 8 ms
10,640 KB
testcase_02 AC 8 ms
10,708 KB
testcase_03 AC 9 ms
10,720 KB
testcase_04 AC 1,778 ms
11,700 KB
testcase_05 AC 914 ms
15,316 KB
testcase_06 AC 2,349 ms
15,780 KB
testcase_07 AC 1,676 ms
13,988 KB
testcase_08 AC 908 ms
12,352 KB
testcase_09 AC 446 ms
11,436 KB
testcase_10 AC 2,043 ms
13,944 KB
testcase_11 AC 30 ms
13,420 KB
testcase_12 AC 517 ms
13,876 KB
testcase_13 AC 2,169 ms
14,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

-- min [ (500/x)^2 + 1000x + x^2 ] ~= 10000 at x ~= 8
local mesh = 8
local boxnum = 125 --math.floor(1001 / mesh)
local s_lowlim = 400 -- x^2 < (x/8)^2 + 16x + 64 where x ~=< 20

local ior = io.input()
local n, k = ior:read("*n", "*n")
local enm_x, enm_y, enm_h = {}, {}, {}
local ex, ey = 0, 0
for i = 1, n do
  ex, ey, enm_h[i] = ior:read("*n", "*n", "*n")
  enm_x[i], enm_y[i] = ex + 500, ey + 500
end

local boxval = {}
local pixval = {}
for i = 1, boxnum * boxnum do boxval[i] = 0 end
for i = 1, 1001 * 1001 do pixval[i] = 0 end

local mmi, mma, mfl = math.min, math.max, math.floor

for i = 1, k do
  local ax, ay, aw, ah, ad = ior:read("*n", "*n", "*n", "*n", "*n")
  local axleft, ayleft = ax + 500, ay + 500
  local axright, ayright = mmi(axleft + aw, 1000), mmi(ayleft + ah, 1000)
  if((aw + 1) * (ah + 1) <= s_lowlim) then
    for i_x = axleft, axright do for i_y = ayleft, ayright do
      local idx = i_y * 1001 + i_x + 1
      pixval[idx] = pixval[idx] + ad
    end end
  else
    local boxxleft, boxyleft = mfl(axleft / mesh), mfl(ayleft / mesh)
    if(axleft % mesh ~= 0) then boxxleft = boxxleft + 1 end
    if(ayleft % mesh ~= 0) then boxyleft = boxyleft + 1 end
    local boxxright, boxyright = mfl(axright / mesh), mfl(ayright / mesh)
    if(axright % mesh ~= mesh - 1) then boxxright = boxxright - 1 end
    if(ayright % mesh ~= mesh - 1) then boxyright = boxyright - 1 end

    local boxxleftpx, boxyleftpx = boxxleft * mesh, boxyleft * mesh
    local boxxrightpx, boxyrightpx = (boxxright + 1) * mesh - 1, (boxyright + 1) * mesh - 1

    local leftedge = mmi(axright, boxxleftpx - 1)
    local rightedge = mma(leftedge + 1, boxxrightpx + 1)
    -- left
    for i_x = axleft, leftedge do for i_y = ayleft, ayright do
      local idx = i_y * 1001 + i_x + 1
      pixval[idx] = pixval[idx] + ad
    end end
    -- right
    for i_x = rightedge, axright do for i_y = ayleft, ayright do
      local idx = i_y * 1001 + i_x + 1
      pixval[idx] = pixval[idx] + ad
    end end

    if(boxxleft <= boxxright) then
      local yleftedge = mmi(ayright, boxyleftpx - 1)
      local yrightedge = mma(yleftedge + 1, boxyrightpx + 1)
      -- center bottom(yleft)
      for i_x = leftedge + 1, rightedge - 1 do for i_y = ayleft, yleftedge do
        local idx = i_y * 1001 + i_x + 1
        pixval[idx] = pixval[idx] + ad
      end end
      -- center top(yright)
      for i_x = leftedge + 1, rightedge - 1 do for i_y = yrightedge, ayright do
        local idx = i_y * 1001 + i_x + 1
        pixval[idx] = pixval[idx] + ad
      end end
      -- center BOX
      if(boxyleft <= boxyright) then
        for i_bx = boxxleft, boxxright do for i_by = boxyleft, boxyright do
          local idx = i_by * boxnum + i_bx + 1
          boxval[idx] = boxval[idx] + ad
        end end
      end

    end
  end
end
local enmhp = 0
for i = 1, n do
  ex, ey = enm_x[i], enm_y[i]
  local ebx, eby = mfl(ex / mesh), mfl(ey / mesh)
  local idx, b_idx = ey * 1001 + ex + 1, eby * boxnum + ebx + 1
  if(b_idx <= boxnum * boxnum) then
    enmhp = enmhp + mma(0, enm_h[i] - pixval[idx] - boxval[b_idx])
  else
    enmhp = enmhp + mma(0, enm_h[i] - pixval[idx])
  end
end
print(enmhp)
0