結果

問題 No.60 魔法少女
ユーザー 👑 obakyanobakyan
提出日時 2019-05-03 20:47:01
言語 Lua
(LuaJit 2.1.1696795921)
結果
WA  
実行時間 -
コード長 3,189 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 5,376 KB
実行使用メモリ 14,336 KB
最終ジャッジ日時 2024-06-10 06:23:51
合計ジャッジ時間 17,162 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
11,008 KB
testcase_01 AC 8 ms
10,952 KB
testcase_02 AC 8 ms
10,944 KB
testcase_03 AC 9 ms
10,968 KB
testcase_04 AC 2,141 ms
12,032 KB
testcase_05 AC 1,058 ms
14,192 KB
testcase_06 AC 2,968 ms
14,208 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 511 ms
11,904 KB
testcase_10 AC 2,566 ms
14,336 KB
testcase_11 WA -
testcase_12 AC 642 ms
14,172 KB
testcase_13 AC 3,030 ms
14,336 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

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 = math.min(axleft + aw, 1000), math.min(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 = math.floor(axleft / mesh), math.floor(ayleft / mesh)
    if(axleft % mesh ~= 0) then boxxleft = boxxleft + 1 end
    if(ayleft % mesh ~= 0) then boxyleft = boxyleft + 1 end
    local boxxright, boxyright = math.floor(axright / mesh), math.floor(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 * mesh - 1, boxyright * mesh - 1

    local leftedge = math.min(axright, boxxleftpx - 1)
    local rightedge = math.max(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 = math.min(ayright, boxyleftpx - 1)
      local yrightedge = math.max(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 = math.floor(ex / mesh), math.floor(ey / mesh)
  local idx, b_idx = ey * 1001 + ex + 1, eby * boxnum + ebx + 1
  if(b_idx <= boxnum * boxnum) then
    enmhp = enmhp + math.max(0, enm_h[i] - pixval[idx] - boxval[b_idx])
  else
    enmhp = enmhp + math.max(0, enm_h[i] - pixval[idx])
  end
end
print(enmhp)
0