Submission #10080104


Source Code Expand

Copy
class MinHeap
  def initialize(source)
    @arr = []
    source.each do |e|
      push(e)
    end
  end

  def size
    @arr.size
  end

  def empty?
    @arr.empty?
  end

  def top
    @arr.first
  end

  # ヒープに値を追加する
  def push(value)
    @arr << value     # 最後尾に追加
    i = @arr.size - 1 # 追加されたノード番号

    # 親子関係を修復していく
    while i > 0
      parent = (i - 1) / 2 # 親のノード番号

      # 親子関係が逆転してなかったら終了
      break if @arr[parent].first <= value.first

      # 親と自分をswap
      @arr[parent], @arr[i] = @arr[i], @arr[parent]

      i = parent
    end

    # 追加したい値は最終的にこの位置に決定する
    @arr[i] = value
  end

  # ヒープから最小値を取り出す
  def pop
    min = top # 最小値 = 返り値

    # ここからヒープを再構築する
    # ひとまず最後尾をルートノードにもっていくる
    tmp_node = @arr.last
    @arr.pop

    # ルートノードから降ろしていく
    i = 0
    while (i * 2 + 1) < size
      # 左側の子が配列のサイズを超えるまで
      # = 左側の子が配列サイズを超えているということは、
      # そのノードには子が存在しないということになる

      # 左右の子ノードの値を比較して小さい方をmin_childとする
      lhs_child = i * 2 + 1 # 左側の子
      rhs_child = i * 2 + 2 # 右側の子
      min_child = lhs_child # とりあえず左側が小さいと仮定しておく(右側の子が存在しないこともあるため)

      if rhs_child < size
        # 右側の子のインデックスが配列のサイズを超えていないとき
        # = 超えているということは、右側の子は存在しないということ
        # => その場合は左側の子が採用される

        if @arr[lhs_child].first > @arr[rhs_child].first
          min_child = rhs_child
        end
      end

      # 逆転していなければ終了
      break if @arr[min_child].first >= tmp_node.first

      # 自分のノードを子の値にする
      @arr[i] = @arr[min_child]
      i = min_child
    end

    # 選んだノードは最終的にこの位置に決定(空なら最後の要素だったということなのでセット不要)
    @arr[i] = tmp_node unless empty?

    min
  end
end

n, k = gets.strip.split.map(&:to_i)
ab = n.times.map { gets.strip.split.map(&:to_i) }

heap = MinHeap.new([])

ab.each do |e|
  heap.push e
end

ans = 0
k.times do
  min = heap.pop
  heap.push([min.first + min.last, min.last])
  ans += min.first
end

puts ans

Submission Info

Submission Time
Task C - Factory
User akht
Language Ruby (2.3.3)
Score 300
Code Size 2782 Byte
Status
Exec Time 1194 ms
Memory 12084 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 8 ms 1916 KB
sample_02.txt 254 ms 1916 KB
sample_03.txt 84 ms 1916 KB
subtask_1_1.txt 11 ms 1788 KB
subtask_1_10.txt 1194 ms 6520 KB
subtask_1_11.txt 7 ms 1788 KB
subtask_1_12.txt 233 ms 10420 KB
subtask_1_13.txt 7 ms 1788 KB
subtask_1_14.txt 280 ms 4660 KB
subtask_1_15.txt 1050 ms 12084 KB
subtask_1_16.txt 124 ms 1788 KB
subtask_1_17.txt 85 ms 1788 KB
subtask_1_18.txt 946 ms 12084 KB
subtask_1_2.txt 677 ms 3708 KB
subtask_1_3.txt 119 ms 6392 KB
subtask_1_4.txt 492 ms 2172 KB
subtask_1_5.txt 242 ms 10420 KB
subtask_1_6.txt 776 ms 2812 KB
subtask_1_7.txt 319 ms 2044 KB
subtask_1_8.txt 962 ms 12084 KB
subtask_1_9.txt 951 ms 10420 KB