Submission #17481985


Source Code Expand

Copy
local function meld(node1,node2)
    if not node1 then
        return node2
    elseif not node2 then
        return node1
    elseif node1[1]<node2[1] then
        node2[4]=node1[3]
        node1[3]=node2
        return node1
    else
        node1[4]=node2[3]
        node2[3]=node1
        return node2
    end
end

local function pairing(node,stack)
    if node and node[4] then
        return pairing(node[4][4],rawset(meld(node,node[4]),4,stack))
    else
        return stack,node
    end
end

local function meld_pairs(stack,node)
    if stack then
        return meld_pairs(stack[4],meld(stack,node))
    else
        return node
    end
end

local PairingHeap={}

PairingHeap.empty=function(self)
    return not self[1]
end

PairingHeap.push=function(self,key,value)
    self[1]=meld(self[1],{key,value,false,false})
end

PairingHeap.ktop=function(self)
    return self[1][1]
end

PairingHeap.vtop=function(self)
    return self[1][2]
end

PairingHeap.pop=function(self)
    self[1]=meld_pairs(pairing(self[1][3],false))
end

PairingHeap.new=function()
    return setmetatable({false},{__index=PairingHeap})
end

----------

local n,k=io.read("n","n")
local pq=PairingHeap:new()
local b={}
for i=1,n do
    pq:push(io.read("n"),i)
    b[i]=io.read("n")
end

local total=0
for j=1,k do
    local a=pq:ktop()
    local i=pq:vtop()
    pq:pop()
    total=total+a
    pq:push(a+b[i],i)
end
print(total)

Submission Info

Submission Time
Task C - Factory
User S97323424
Language Lua (Lua 5.3.5)
Score 300
Code Size 1484 Byte
Status
Exec Time 520 ms
Memory 32432 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
× 3
× 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt 5 ms 2664 KB
sample_02.txt 109 ms 2744 KB
sample_03.txt 59 ms 2700 KB
subtask_1_1.txt 9 ms 2792 KB
subtask_1_10.txt 128 ms 25128 KB
subtask_1_11.txt 2 ms 2644 KB
subtask_1_12.txt 97 ms 18412 KB
subtask_1_13.txt 2 ms 2740 KB
subtask_1_14.txt 143 ms 9964 KB
subtask_1_15.txt 509 ms 32432 KB
subtask_1_16.txt 64 ms 2640 KB
subtask_1_17.txt 54 ms 2792 KB
subtask_1_18.txt 173 ms 26576 KB
subtask_1_2.txt 297 ms 7328 KB
subtask_1_3.txt 62 ms 10084 KB
subtask_1_4.txt 252 ms 3292 KB
subtask_1_5.txt 121 ms 18472 KB
subtask_1_6.txt 179 ms 4956 KB
subtask_1_7.txt 148 ms 2900 KB
subtask_1_8.txt 520 ms 26324 KB
subtask_1_9.txt 498 ms 29216 KB